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

发表于 分类于 阅读次数：

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

解法1：BFS

思路：

额外空间复杂度O（n）

bfs广度优先搜索

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
class Solution {
public:
    Node* connect(Node* root) {
        if(root==NULL)
            return root;
        queue<Node *> que;
        que.push(root);
        Node *p=new Node(0);
        while(!que.empty())
        {
            int n=que.size();
            for(int i=0;i<n;i++)
            {
                p=que.front();
                que.pop();
                if(i==n-1)
                {}
                else
                {
                    p->next=que.front();
                }
                if(p->left!=NULL)   que.push(p->left);
                if(p->right!=NULL)  que.push(p->right);
            }
        }
        return root;
    }
};

解法2：递归

前序遍历，判断其每个节点的左孩子以及若有next节点，使其右孩子的next链到next的左孩子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    Node* connect(Node* root) {
        if(root==NULL)
            return NULL;
        if(root->left!=NULL)
        {
            root->left->next=root->right;
            if(root->next!=NULL)
            {
                root->right->next=root->next->left;
            }
        }
        connect(root->left);
        connect(root->right);
        return root;
    }
};

解法3：迭代

思考：

每一次都是从最左边的左孩子开始，每向下一层都将上面的全部链接好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    Node* connect(Node* root) {
        auto pre=root;
        while(pre!=NULL)
        {
            auto cur=pre;
            while(cur!=NULL)
            {
                if(cur->left!=NULL)
                    cur->left->next=cur->right;
                if(cur->right!=NULL&&cur->next!=NULL)
                {
                    cur->right->next=cur->next->left;
                }
                cur=cur->next;
            }
            pre=pre->left;
        }
        return root;
    }
};