Populating Next Right Pointers in Each Node

Given a binary tree

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

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

Initially, all next pointers are set toNULL.

Note:

• You may only use constant extra space.

• Recursive approach is fine, implicit stack space does not count as extra space for this problem.

• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

Example:

Given the following perfect binary tree,

     1
   /  \
  2    3
 / \  / \
4  5  6  7

After calling your function, the tree should look like:

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

Analysis

Non-recursion

非递归的方法就是遍历Binary Tree，由于条件限制不能用额外空间extra space，因此level order BFS 所需的queue就不能用了。好在这一题中每层之间最终都会通过指针连接起来，也就让一行之内的遍历成为可能。

在上一层的节点连接起来之后就可以遍历该层，并且连接下一层的子节点。连接子节点分为两种情形：

1. 该节点的左右子节点进行连接

2. 该节点的右子节点和同层邻近下一个节点的左子节点相连接

层内移动指针：

curr = curr.next;

转到下一层：

levelStart = levelStart.left;

Recursion

递归的inexplicit的调用栈不在题目条件的限制内，因此也可以用递归。

递归函数的逻辑其实挺简单，就是把节点1连接到节点2

node1.next = node2

Solution

Use level start TreeLinkNode - O(1) space, O(n) time

/**
 * 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) {
        if (root == null) {
            return;
        }
        TreeLinkNode levelStart = root;
        // Move across level
        while (levelStart != null) {
            TreeLinkNode curr = levelStart;
            // Move within level
            while (curr != null) {
                if (curr.left != null)  curr.left.next = curr.right; 
                if (curr.right != null && curr.next != null) curr.right.next = curr.next.left;
                curr = curr.next;
            }
            levelStart = levelStart.left;
        }
    }
}

Use recursion - (3ms 29.60%)

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        connectHelper(root.left, root.right);
    }
    private void connectHelper(TreeLinkNode node1, TreeLinkNode node2) {
        if (node1 == null || node2 == null) {
            return;
        } 
        node1.next = node2;
        connectHelper(node1.left, node1.right);
        connectHelper(node1.right, node2.left);
        connectHelper(node2.left, node2.right);
    }
}