117. Populating Next Right Pointers in Each Node II

Leetcode Tree Depth-first Search

Given a binary tree

public class TreeLinkNode {
  int val;
  TreeLinkNode left, right, next;
  TreeLinkNode(int x) { val = x; }
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• Recursive approach is fine, implicit stack space does not count as extra space for this problem.

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

分析

这道题目几乎和116. Populating Next Right Pointers in Each Node一摸一样，只是去掉了条件--二叉树是完全二叉树。那么Q116中的解法1，解法2仍旧可以使用。问题是解法3可以使用吗？或者需要怎么样的更改？由于不是完全二叉树，需要增加一些判断，还需要保存每一层的开始位置，仅此而已。

public void connect(TreeLinkNode root) {
    TreeLinkNode next_head = null; //head of the next level
    TreeLinkNode next_prev = null; //the leading node on the next level
    TreeLinkNode cur = root;  //current node of current level

    while (cur != null) { // travel on diff levels
        while (cur != null) { //iterate on the current level
            //left child
            if (cur.left != null) {
                if (next_prev != null) next_prev.next = cur.left;
                else next_head = cur.left;
                next_prev = cur.left;
            }
            //right child
            if (cur.right != null) {
                if (next_prev != null) next_prev.next = cur.right;
                else next_head = cur.right;
                next_prev = cur.right;
            }
            //move to next node
            cur = cur.next;
        }

        // move to next level
        cur = next_head;
        next_head = null;
        next_prev = null;
    }
}