Populating Next Right Pointers in Each Node II--leetcode难题讲解系列

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,

After calling your function, the tree should look like:

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

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

由于空间复杂度为O（1），广搜深搜不能使用，只能考虑递归迭代。充分利用parent的next指针，我们可以很容易的找到子节点的next指针。

// C++ RECURSIVE CODE: 
class Solution {
public:
    static void connect(TreeLinkNode* root){
        if(root == NULL) return;
        if(root->left) root->left->next = root->right;
        if(root->next && root->right ) root->right->next = root->next->left;
        connect(root->left);
        connect(root->right);
    }
};

实际上用栈也是会消耗空间的，迭代应该是最合适的办法。为了保持处理的一致性，我们可以给每一层加一个dummy头结点，然后根据parent层（利用next）决定child层的next。

// JAVA ITERATIVE CODE:
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode dummy = new TreeLinkNode(0);
        while(root != null){
            TreeLinkNode child = dummy;
            dummy.next = null;
            while(root != null){
                if(root.left != null){
                    child.next = root.left;
                    child = child.next;
                }
                if(root.right != null){
                    child.next = root.right;
                    child = child.next;
                }
                root = root.next;
            }
            root = dummy.next;
        }
    }
}

PYTHON ITERATIVE CODE：

class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        dummychild = TreeLinkNode(0)
        while root:
            cur = dummychild
            dummychild.next = None
            while root:
                if root.left:
                    cur.next = root.left
                    cur = cur.next
                if root.right:
                    cur.next = root.right
                    cur = cur.next
                root = root.next
            root = dummychild.next

View Code

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,

After calling your function, the tree should look like:

         1 -> NULL
       /  
      2 -> 3 -> NULL
     /     
    4-> 5 -> 7 -> NULL
https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/


唯一的区别是找子节点的next指针不是那么直接了，可以用函数根据不同情况来返回，其他的部分做法一样。

class Solution {
public:
    TreeLinkNode* first(TreeLinkNode* root){
        root = root->next;
        while(root){
            if(root->left) return root->left;
            else if(root->right) return root->right;
            root = root->next;
        }
        return NULL;
    }
    void connect(TreeLinkNode* cur){
        TreeLinkNode* root = cur;
        if(root == NULL) return;
        while(root){
            if(root->left){
                root->left->next = root->right ? root->right: first(root);
            }
            if(root->right){
                root->right->next = first(root);
            }
            root = root->next;
        }
        connect(cur->left);
        connect(cur->right);
    }
};