康瑞部落

Populating Next Right Pointers in Each Node II

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,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

解题思路：

与Populating Next Right Pointers in Each Node类似，只是这里的二叉树是任意的二叉树。我们需要记录某层第一个拥有孩子节点的树节点。分情况讨论，情况的分支在代码中注释了

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root==NULL){
            return;
        }
        TreeLinkNode* upLayerFirstNode = root;
        TreeLinkNode* upLayerNode = root;
        TreeLinkNode* node = root->left==NULL ? root->right : root->left;
        while(node!=NULL){
            bool findUpLayerFirstNode = false;
            while(upLayerNode!=NULL){
                if(!findUpLayerFirstNode && (node->left!=NULL || node->right!=NULL)){
                    upLayerFirstNode = node;
                    findUpLayerFirstNode = true;
                }
                if(upLayerNode->left == node){  //当前节点为上层节点的左孩子节点
                    if(upLayerNode->right!=NULL){
                        node->next = upLayerNode->right;
                        node = node->next;
                        upLayerNode = upLayerNode->next;
                    }else{
                        upLayerNode = upLayerNode->next;
                    }
                }else if(upLayerNode->right == node){ //当前节点为上层节点的右孩子节点
                    upLayerNode = upLayerNode->next;
                }else if(upLayerNode->left!=NULL){  //当前节点均不是上层节点的左右孩子节点，且上层节点存在左孩子节点
                    node->next = upLayerNode->left;
                    node = node->next;
                }else if(upLayerNode->right!=NULL){ //上层节点不存在左孩子节点，但存在右孩子节点，且右孩子节点不是当前节点
                    node->next = upLayerNode->right;
                    node = node->next;
                    upLayerNode = upLayerNode->next;
                }else{                              //上层节点不存在孩子节点
                    upLayerNode = upLayerNode->next;
                }
                if(!findUpLayerFirstNode && (node->left!=NULL || node->right!=NULL)){   //注意这里还需要判断一下，因为当期节点有可能next操作了
                    upLayerFirstNode = node;
                    findUpLayerFirstNode = true;
                }
            }
            if(findUpLayerFirstNode){
                upLayerNode=upLayerFirstNode;
                node = upLayerFirstNode->left==NULL ? upLayerFirstNode->right : upLayerFirstNode->left;
            }else{
                node = NULL;
            }
        }
    }
};