怎樣python二叉樹中的右側(cè)指針

怎樣python二叉樹中的右側(cè)指針，相信很多沒有經(jīng)驗(yàn)的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個(gè)問題。

給定一個(gè)完美二叉樹，其所有葉子節(jié)點(diǎn)都在同一層，每個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。二叉樹定義如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。

初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。 

示例：

輸入：{"$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}

輸出：{"$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}

解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個(gè) next 指針，以指向其下一個(gè)右側(cè)節(jié)點(diǎn)，如圖 B 所示。

解題思路：

1，樹問題均可遞歸

2，先填充一層，然后遞歸處理左右子樹

3，由于是完美二叉樹，處理簡單：

左子樹的next是右子樹，?????子樹的next是next的左子樹

/*// Definition for a Node.class Node {public:    int val;    Node* left;    Node* right;    Node* next;
    Node() {}
    Node(int _val, Node* _left, Node* _right, Node* _next) {        val = _val;        left = _left;        right = _right;        next = _next;    }};*/class Solution {public:    Node* connect(Node* root) {        if(root==NULL || root->left==NULL){            return root;        }        root->left->next=root->right;        if(root->next!=NULL){            root->right->next=root->next->left;        }        connect( root->left);        connect(root->right);        return root;    }};

給定一個(gè)二叉樹

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。

初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。

示例：

輸入：{"$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":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

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

解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個(gè) next 指針，以指向其下一個(gè)右側(cè)節(jié)點(diǎn)，如圖 B 所示。

提示：

• 你只能使用常量級額外空間。

• 使用遞歸解題也符合要求，本題中遞歸程序占用的?？臻g不算做額外的空間復(fù)雜度

解題思路：

1，本題與上題的唯一不同是不是完美二叉樹

2，因此需要計(jì)算next節(jié)點(diǎn)是什么：

A，左子樹（若非空）

B，右子樹（若非空）

C，next的子樹

3，左子樹的next 節(jié)點(diǎn)有兩種情況：

A，右子樹（若非空）

B，next（或next的next）節(jié)點(diǎn)的子樹

4，右子樹的next節(jié)點(diǎn)：next（或next的next）節(jié)點(diǎn)的子樹

5，由于計(jì)算next節(jié)點(diǎn)依賴右子樹，所以先遞歸右子樹

/*// Definition for a Node.class Node {public:    int val;    Node* left;    Node* right;    Node* next;
    Node() {}
    Node(int _val, Node* _left, Node* _right, Node* _next) {        val = _val;        left = _left;        right = _right;        next = _next;    }};*/class Solution {public:    Node* connect(Node* root) {        if (root==NULL){            return NULL;        }                if (root->left!=NULL){            if(root->right!=NULL){                root->left->next=root->right;            }else{                root->left->next=nextNode(root->next);            }        }                if(root->right!=NULL){         root->right->next=nextNode(root->next);           }        connect(root->right);        connect(root->left);        return root;    }    Node* nextNode(Node* root){       Node* t=root;        while(t!=NULL){            if (t->left!=NULL){                return t->left;            }            if (t->right!=NULL){                return t->right;            }            t=t->next;        }        return NULL;    }};

看完上述內(nèi)容，你們掌握怎樣python二叉樹中的右側(cè)指針的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！