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

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ù)，原本的完全二叉樹的條件不再滿足，但是整體的思路還是很相似，仍然有遞歸和非遞歸的解法。我們先來(lái)看遞歸的解法，這里由于子樹有可能殘缺，故需要平行掃描父節(jié)點(diǎn)同層的節(jié)點(diǎn)，找到他們的左右子節(jié)點(diǎn)。代碼如下：

解法一：

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;
    }
};

對(duì)于非遞歸的方法，我驚喜的發(fā)現(xiàn)之前的方法直接就能用，完全不需要做任何修改，算法思路可參見(jià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;
    }
};

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

這里再來(lái)說(shuō)下 dummy 結(jié)點(diǎn)是怎樣指向每層的首結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的，過(guò)程是這樣的，dummy 是創(chuàng)建出來(lái)的一個(gè)新的結(jié)點(diǎn)，其目的是為了指向 root 結(jié)點(diǎn)的下一層的首結(jié)點(diǎn)的前一個(gè)，具體是這么做到的呢，主要是靠 cur 指針，首先 cur 指向 dummy，然后 cur 再連上 root 下一層的首結(jié)點(diǎn)，這樣 dummy 也就連上了。然后當(dāng) root 層遍歷完了之后，root 需要往下移動(dòng)一層，這樣 dummy 結(jié)點(diǎn)之后連接的位置就正好賦值給 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++實(shí)現(xiàn)LeetCode(117.每個(gè)節(jié)點(diǎn)的右向指針之二)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)每個(gè)節(jié)點(diǎn)的右向指針之二內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論