Leetcode-117. 填充每个节点的下一个右侧节点指针 II

发表于 分类于 阅读次数：

题目：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/

解法1：迭代

与116题类似

加一个指针变量存当前位置指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    Node* connect(Node* root) {
        auto pre=root;
        while(pre!=NULL)
        {
            //注意这里，由于不是完美二叉树，有些同一层节点有的是叶子节点，而有的还有孩子节点
            while(pre&&pre->left==NULL&&pre->right==NULL)   pre=pre->next;
            if(pre==NULL)
                break;
            auto temp=pre;
            Node *cur=NULL;
            while(temp!=NULL)
            {
                if(temp->left!=NULL)
                {
                    if(cur!=NULL)
                        cur->next=temp->left;
                    cur=temp->left;
                }
                if(temp->right!=NULL)
                {
                    if(cur!=NULL)
                        cur->next=temp->right;
                    cur=temp->right;
                }
                temp=temp->next;
            }
            pre=pre->left!=NULL?pre->left:pre->right;
        }
        return root;
    }
};