怎樣python二叉樹中的右側指針

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

給定一個完美二叉樹，其所有葉子節點都在同一層，每個父節點都有兩個子節點。二叉樹定義如下：

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

填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。

初始狀態下，所有 next 指針都被設置為 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 所示，你的函數應該填充它的每個 next 指針，以指向其下一個右側節點，如圖 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;    }};

給定一個二叉樹

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

填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。

初始狀態下，所有 next 指針都被設置為 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 所示，你的函數應該填充它的每個 next 指針，以指向其下一個右側節點，如圖 B 所示。

提示：

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

• 使用遞歸解題也符合要求，本題中遞歸程序占用的棧空間不算做額外的空間復雜度

解題思路：

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

2，因此需要計算next節點是什么：

A，左子樹（若非空）

B，右子樹（若非空）

C，next的子樹

3，左子樹的next 節點有兩種情況：

A，右子樹（若非空）

B，next（或next的next）節點的子樹

4，右子樹的next節點：next（或next的next）節點的子樹

5，由于計算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){            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;    }};

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