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

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.

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

對于非遞歸的解法要稍微復(fù)雜一點(diǎn)，但也不算特別復(fù)雜，需要用到 queue 來輔助，由于是層序遍歷，每層的節(jié)點(diǎn)都按順序加入 queue 中，而每當(dāng)從 queue 中取出一個(gè)元素時(shí)，將其 next 指針指向 queue 中下一個(gè)節(jié)點(diǎn)即可，對于每層的開頭元素開始遍歷之前，先統(tǒng)計(jì)一下該層的總個(gè)數(shù)，用個(gè) for 循環(huán)，這樣當(dāng) for 循環(huán)結(jié)束的時(shí)候，該層就已經(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;
    }
};

我們再來看下面這種碉堡了的方法，用兩個(gè)指針 start 和 cur，其中 start 標(biāo)記每一層的起始節(jié)點(diǎn)，cur 用來遍歷該層的節(jié)點(diǎn)，設(shè)計(jì)思路之巧妙，不得不服啊：

解法三：

// 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

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