leetCode 117.Populating Next Right Pointers in Each Node II （替节点添加右指针） 解题思路和方法

leetCode 117.Populating Next Right Pointers in Each Node II （为节点添加右指针） 解题思路和方法

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

思路：此题与上一题最大的差别是二叉树非完美二叉树，所以在用上一层右指针寻找下一个水平序节点是需要判断左右子树是否存在。

具体代码如下：

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        dfs(root);
    }
    
    /**
     * dfs，从上一层的节点next指针遍历
     * 取得当前层的q，寻找下一个不为空的节点
     * 将q.next指向节点，然后q = q.next即可
     * 
     */ 
    private void dfs(TreeLinkNode root){
        if(root == null){
            return;
        }
        TreeLinkNode p = root;
        TreeLinkNode q = null;
        
        while(root != null){
        	if(root.left != null){
        		q = next(q, root.left);
        	}
        	if(root.right != null){
        		q = next(q,root.right);
        	}
        	root = root.next;
        }
        
        //寻找下一层的第一个元素
        while(p != null){
        	if(p.left != null){
        		dfs(p.left);
        		break;
        	}else if(p.right != null){
        		dfs(p.right);
        		break;
        	}else{
        		p = p.next;
        	}
        }
    }
    //确定next指向节点
    private TreeLinkNode next(TreeLinkNode q,TreeLinkNode r){
    	if(q == null){
			q = r;
		}else if(q.next == null){
			q.next = r;
			q = q.next;
		}
    	return q;
    }
}