[C++] LeetCode 117. 填充同一层的兄弟节点 II

题目

给定一个二叉树

填充它的每个

next

指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将

next

指针设置为

NULL

。

初始状态下，所有

next

指针都被设置为

NULL

。

说明:

1. 你只能使用额外常数空间。

2. 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例:

给定二叉树，

调用你的函数后，该二叉树变为：

代码

/**
 * 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 *node=root,*tmp=root;
        while(root){
            if(root->left&&root->right)
                root->left->next=root->right;
            else if(root->left==NULL&&root->right==NULL){
                root=root->next;
                continue;
            }
            tmp=root->next;
            while(tmp&&tmp->left==NULL&&tmp->right==NULL) tmp=tmp->next;
            if(tmp!=NULL){
                if(root->right!=NULL)
                    root->right->next=tmp->left!=NULL?tmp->left:tmp->right;
                else if(root->left!=NULL)
                    root->left->next=tmp->left!=NULL?tmp->left:tmp->right;
            }
            root=tmp;
        }
        while(node&&node->left==NULL&&node->right==NULL) node=node->next;
        if(node==NULL) return;
        else if(node->left)
            connect(node->left);
        else
            connect(node->right);
    }
};           

非递归写法

/**
 * 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;
        while(root){
            TreeLinkNode* node=root,*t=NULL;
            while(node){
                if(node->left!=NULL&&node->right!=NULL) node->left->next=node->right;
                else if(node->left==NULL&&node->right==NULL){
                    node=node->next;
                    continue;
                }
                if(t==NULL) t=node;
                TreeLinkNode *tmp=node->next;
                while(tmp&&tmp->left==NULL&&tmp->right==NULL) tmp=tmp->next;
                if(tmp!=NULL&&node->right!=NULL) node->right->next=tmp->left!=NULL?tmp->left:tmp->right;
                else if(tmp!=NULL&&node->left!=NULL) node->left->next=tmp->left!=NULL?tmp->left:tmp->right;
                node=tmp;
            }
            if(t==NULL) return;
            root=t->left==NULL?t->right:t->left;
        }
    }
};