leetcode：Populating Next Right Pointers in Each Node II （顺序联接二叉树每一层节点）【面试算法题】

leetcode：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,

After calling your function, the tree should look like:

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

题意把二叉树每一层所有的节点顺序链接，只能开辟常数空间。

这题与上道题不同点在于二叉树不是完全二叉树，因此结构差别较大，不能用上道题的方法。

如果当前节点有左右子节点，先把他们链接起来，因为肯定是相邻的。

然后通过root的next指针，找到需要与当前节点子节点连接的后继节点。

因为涉及到root的next指针查询，递归需要先处理完右子树，以便左子树节点next指针的连接。

/**
 * 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)return;
            TreeLinkNode *temp=root->next,*p;
            if(root->left &&root->right)
            {
                p=root->right;
                root->left->next = root->right;
            }
            else if(root->right)p=root->right;
            else if(root->left)p=root->left;
            else p=NULL;
            if(p)
            {
                while(temp)
                {
                    if(temp->left)
                    {
                        p->next = temp->left;
                        break;
                    }
                    else if(temp->right)
                    {
                        p->next = temp->right;
                        break;
                    }
                    else temp=temp->next;
                }
            }
            connect(root->right);
            connect(root->left);
            
        }
};
// http://blog.csdn.net/havenoidea

题解目录

leetcode：Populating Next Right Pointers in Each Node II （顺序联接二叉树每一层节点）【面试算法题】

相关推荐