怎样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二叉树中的右侧指针的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注行业资讯频道，感谢各位的阅读！