C++實現LeetCode(117.每個節點的右向指針之二)

Posted on by

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

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

解法一：

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

對於非遞歸的方法，我驚喜的發現之前的方法直接就能用，完全不需要做任何修改，算法思路可參見之前的博客 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 結點來指向每層的首結點的前一個結點，然後指針 cur 用來遍歷這一層，這裡實際上是遍歷一層，然後連下一層的 next，首先從根結點開始，如果左子結點存在，那麼 cur 的 next 連上左子結點，然後 cur 指向其 next 指針；如果 root 的右子結點存在，那麼 cur 的 next 連上右子結點，然後 cur 指向其 next 指針。此時 root 的左右子結點都連上瞭，此時 root 向右平移一位，指向其 next 指針，如果此時 root 不存在瞭，說明當前層已經遍歷完瞭，重置 cur 為 dummy 結點，root 此時為 dummy->next，即下一層的首結點，然後 dummy 的 next 指針清空，或者也可以將 cur 的 next 指針清空，因為前面已經將 cur 賦值為 dummy 瞭。那麼現在想一想，為什麼要清空？因為用 dummy 的目的就是要指到下一行的首結點的位置即 dummy->next，而一旦將 root 賦值為 dummy->next 瞭之後，這個 dummy 的使命就已經完成瞭，必須要斷開，如果不斷開的話，那麼假設現在 root 是葉結點瞭，那麼 while 循環還會執行，不會進入前兩個 if，然後 root 右移賦空之後，會進入最後一個 if，之前沒有斷開 dummy->next 的話，那麼 root 又指向之前的葉結點瞭，死循環誕生瞭，跪瞭。所以一定要記得清空哦。

這裡再來說下 dummy 結點是怎樣指向每層的首結點的前一個結點的，過程是這樣的，dummy 是創建出來的一個新的結點，其目的是為瞭指向 root 結點的下一層的首結點的前一個，具體是這麼做到的呢，主要是靠 cur 指針，首先 cur 指向 dummy，然後 cur 再連上 root 下一層的首結點，這樣 dummy 也就連上瞭。然後當 root 層遍歷完瞭之後，root 需要往下移動一層，這樣 dummy 結點之後連接的位置就正好賦值給 root，然後 cur 再指向 dummy，dummy 之後斷開，這樣又回到瞭初始狀態，以此往復就可以都連上瞭，代碼如下：

解法三： 

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

到此這篇關於C++實現LeetCode(117.每個節點的右向指針之二)的文章就介紹到這瞭,更多相關C++實現每個節點的右向指針之二內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：