[LeetCode] 117. Populating Next Right Pointers in Each Node II 每個節(jié)點的右向指針之二

Given a binary tree

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

• The number of nodes in the given tree is less than 6000.
• -100 <= node.val <= 100

這道是之前那道 Populating Next Right Pointers in Each Node 的延續(xù)，原本的完全二叉樹的條件不再滿足，但是整體的思路還是很相似，仍然有遞歸和非遞歸的解法。我們先來看遞歸的解法，這里由于子樹有可能殘缺，故需要平行掃描父節(jié)點同層的節(jié)點，找到他們的左右子節(jié)點。代碼如下：

解法一：

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return NULL;
        Node *p = root->next;
        while (p) {
            if (p->left) {
                p = p->left;
                break;
            }
            if (p->right) {
                p = p->right;
                break;
            }
            p = p->next;
        }
        if (root->right) root->right->next = p; 
        if (root->left) root->left->next = root->right ? root->right : p; 
        connect(root->right);
        connect(root->left);
        return root;
    }
};

對于非遞歸的方法，我驚喜的發(fā)現(xiàn)之前的方法直接就能用，完全不需要做任何修改，算法思路可參見之前的博客 Populating Next Right Pointers in Each Node，代碼如下：

解法二：

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return NULL;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int len = q.size();
            for (int i = 0; i < len; ++i) {
                Node *t = q.front(); q.pop();
                if (i < len - 1) t->next = q.front();
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return root;
    }
};

雖然以上的兩種方法都能通過 OJ，但其實它們都不符合題目的要求，題目說只能使用 constant space，可是 OJ 卻沒有寫專門檢測 space 使用情況的 test，那么下面貼上 constant space 的解法，這個解法也是用的層序遍歷，只不過沒有使用 queue 了，我們建立一個 dummy 結(jié)點來指向每層的首結(jié)點的前一個結(jié)點，然后指針 cur 用來遍歷這一層，這里實際上是遍歷一層，然后連下一層的 next，首先從根結(jié)點開始，如果左子結(jié)點存在，那么 cur 的 next 連上左子結(jié)點，然后 cur 指向其 next 指針；如果 root 的右子結(jié)點存在，那么 cur 的 next 連上右子結(jié)點，然后 cur 指向其 next 指針。此時 root 的左右子結(jié)點都連上了，此時 root 向右平移一位，指向其 next 指針，如果此時 root 不存在了，說明當(dāng)前層已經(jīng)遍歷完了，重置 cur 為 dummy 結(jié)點，root 此時為 dummy->next，即下一層的首結(jié)點，然后 dummy 的 next 指針清空，或者也可以將 cur 的 next 指針清空，因為前面已經(jīng)將 cur 賦值為 dummy 了。那么現(xiàn)在想一想，為什么要清空？因為用 dummy 的目的就是要指到下一行的首結(jié)點的位置即 dummy->next，而一旦將 root 賦值為 dummy->next 了之后，這個 dummy 的使命就已經(jīng)完成了，必須要斷開，如果不斷開的話，那么假設(shè)現(xiàn)在 root 是葉結(jié)點了，那么 while 循環(huán)還會執(zhí)行，不會進(jìn)入前兩個 if，然后 root 右移賦空之后，會進(jìn)入最后一個 if，之前沒有斷開 dummy->next 的話，那么 root 又指向之前的葉結(jié)點了，死循環(huán)誕生了，跪了。所以一定要記得清空哦。

這里再來說下 dummy 結(jié)點是怎樣指向每層的首結(jié)點的前一個結(jié)點的，過程是這樣的，dummy 是創(chuàng)建出來的一個新的結(jié)點，其目的是為了指向 root 結(jié)點的下一層的首結(jié)點的前一個，具體是這么做到的呢，主要是靠 cur 指針，首先 cur 指向 dummy，然后 cur 再連上 root 下一層的首結(jié)點，這樣 dummy 也就連上了。然后當(dāng) root 層遍歷完了之后，root 需要往下移動一層，這樣 dummy 結(jié)點之后連接的位置就正好賦值給 root，然后 cur 再指向 dummy，dummy 之后斷開，這樣又回到了初始狀態(tài)，以此往復(fù)就可以都連上了，代碼如下：

解法三： 

class Solution {
public:
    Node* connect(Node* root) {
        Node *dummy = new Node(-1), *cur = dummy, *head = root;
        while (root) {
            if (root->left) {
                cur->next = root->left;
                cur = cur->next;
            }
            if (root->right) {
                cur->next = root->right;
                cur = cur->next;
            }
            root = root->next;
            if (!root) {
                cur = dummy;
                root = dummy->next;
                dummy->next = NULL;
            }
        }
        return head;
    }
};

類似題目：

Populating Next Right Pointers in Each Node

參考資料：

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

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/37813/java-solution-with-constant-space

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/37828/o1-space-on-complexity-iterative-solution

到此這篇關(guān)于C++實現(xiàn)LeetCode(117.每個節(jié)點的右向指針之二)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)每個節(jié)點的右向指針之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論