C++怎么解決每個節(jié)點的右向指針問題

這篇文章主要介紹“C++怎么解決每個節(jié)點的右向指針問題”的相關(guān)知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C++怎么解決每個節(jié)點的右向指針問題”文章能幫助大家解決問題。

每個節(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.

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

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

關(guān)于“C++怎么解決每個節(jié)點的右向指針問題”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點。