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

You may only use constant extra space.

 * 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) {
        TreeLinkNode first = root;  //每层第一个
        while (first != null) {
            TreeLinkNode cur = first;
            TreeLinkNode prev = null;
            while (cur != null) {
                if (cur.left != null) {
                    if (prev != null) {
                        prev.next = cur.left;
                    } else {
                        first = cur.left;
                    }
                    prev = cur.left;
                }
                if (cur.right != null) {
                    if (prev != null) {
                        prev.next = cur.right;
                    } else {
                        first = cur.right;
                    }
                    prev = cur.right;
                }
                cur = cur.next;
            }
            //当没有孩子时, break
            if (cur == null && prev == null) {
                break;
            }
        }
    }
}

若没有空间限制,level order traversal

results matching ""

    No results matching ""