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

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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.

Example:

Input: {"$id":"1","left":{"$id":"2","left":"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

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

這道題實際上是樹的層序遍歷的應用，可以參考之前的博客 Binary Tree Level Order Traversal，既然是遍歷，就有遞歸和非遞歸兩種方法，最好兩種方法都要掌握，都要會寫。下面先來看遞歸的解法，由于是完全二叉樹，所以若節(jié)點的左子結點存在的話，其右子節(jié)點必定存在，所以左子結點的 next 指針可以直接指向其右子節(jié)點，對于其右子節(jié)點的處理方法是，判斷其父節(jié)點的 next 是否為空，若不為空，則指向其 next 指針指向的節(jié)點的左子結點，若為空則指向 NULL，代碼如下：

解法一：

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

對于非遞歸的解法要稍微復雜一點，但也不算特別復雜，需要用到 queue 來輔助，由于是層序遍歷，每層的節(jié)點都按順序加入 queue 中，而每當從 queue 中取出一個元素時，將其 next 指針指向 queue 中下一個節(jié)點即可，對于每層的開頭元素開始遍歷之前，先統(tǒng)計一下該層的總個數(shù)，用個 for 循環(huán)，這樣當 for 循環(huán)結束的時候，該層就已經(jīng)被遍歷完了，參見代碼如下：

解法二：

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

我們再來看下面這種碉堡了的方法，用兩個指針 start 和 cur，其中 start 標記每一層的起始節(jié)點，cur 用來遍歷該層的節(jié)點，設計思路之巧妙，不得不服?。?/p>

解法三：

// Non-recursion, constant space
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return NULL;
        Node *start = root, *cur = NULL;
        while (start->left) {
            cur = start;
            while (cur) {
                cur->left->next = cur->right;
                if (cur->next) cur->right->next = cur->next->left;
                cur = cur->next;
            }
            start = start->left;
        }
        return root;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/116

類似題目：

Populating Next Right Pointers in Each Node II

Binary Tree Right Side View

參考資料：

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

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37473/My-recursive-solution(Java)

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37472/A-simple-accepted-solution

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

最新評論