Populating Next Right Pointers in Each Node

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 to NULL.
Initially, all next pointers are set to NULL.
Note:

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

For 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 

Naive Way: 这里有一个重要限制是constant space.所以不能用stack或者queue来进行遍历。

这里有个问题困扰了我，如何在不用extra space的前提下遍历一颗无父指针二叉树呢。答案是不可能的！

因为二叉树有两个分支，无论先遍历哪一边分支，都必须要记下兄弟节点，否则一旦往下走就不能回头。

而且光记录一个兄弟节点还不行，必须把同一层的兄弟节点都记录下来，这样是和BFS，DFS相对应的O(n)

space。

明白这一点很重要，说明这道题在坑人。

终于过了好久，我发现这道题的next指针导致了我们可以用constant space去遍历一整棵树。 

因为如果我们知道next指针，就可以通过父节点的next指针访问到同一层的兄弟节点。也就是说，

我们不仅要连起这些next指针，还要利用之前连好的这些next指针方便我们连下一层的next指针。

简单的逻辑描述为：

如果一个节点为左节点，其next为父亲的右节点。

如果一个节点为右节点，其next为父亲节点的next节点的左节点（如果有的话）。

并且由于next指针是从左指向右的，我觉得应该从左往右进行遍历。通过next获得下一个要

处理的节点。

写点有点别扭，用了一个do-while语句。但是思想应该是对的。一层一层来，从左到右，

每一层都要记下最左边的子节点，作为下一层遍历的开头。

/**

 * 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 leftMost = root;
        TreeLinkNode node = null;
        while(leftMost.right!=null && leftMost.left!=null){
            node = leftMost;
            leftMost = node.left;
            do{
                node.left.next = node.right;
                node.right.next = node.next==null?null:node.next.left;
                node = node.next;
            }while(node!=null);
        }
    }
}