es网站建设,从网站栏目看网站功能,广东东莞公司,白云区建材网站建设推广后继节点#xff1a;中序遍历的后一个节点
普通二叉树#xff1a;中序遍历得到一个list#xff0c;时间复杂度O(n)
本题的二叉树#xff1a;有父节点的指针#xff0c;后继节点与原节点的距离为1#xff0c;因此可以直接通过父节点找到下一个节点
优化#xff1a;节点…
后继节点中序遍历的后一个节点
普通二叉树中序遍历得到一个list时间复杂度O(n)
本题的二叉树有父节点的指针后继节点与原节点的距离为1因此可以直接通过父节点找到下一个节点
优化节点到另一个节点的真实距离为k时间复杂度为O(k) 情况分析
情况一节点node有右子树后继节点为右子树上的最左节点
情况二节点node无右子树沿着node向上找第一个作为左孩子的祖先左孩子的父节点就是node的后继节点因为此时节点node为节点Y左子树最右侧的节点 对于情况二在找到节点Y之后节点Y即为node的后继节点节点Y有没有右子树不重要
情况三节点node本身为整颗二叉树最右的节点没有后继节点返回null package binarytree;public class SuccessorNode {public class Node {int value;Node left;Node right;Node father;//这里定头节点的father节点为null在创建二叉树时需要注意public Node(int data) {this.value data;}}public Node getsuccessorNode(Node node) {if (node null) {return node;}if (node.right ! null) {//节点node有右子树while (node.left ! null) {//找到最左的节点node node.left;}return node;//返回右子树的最左节点} else {//没有右子树向上找//node不为父节点的左孩子 并且 node的父节点不为null 则向上找while (node ! node.father.left node.father ! null) {node node.father;//此时为第一个不为右孩子的节点此时为第一个为左孩子的节点}node node.father;//如果node不是整颗二叉树的最右的节点返回左孩子的父节点//如果node是整颗二叉树的最右的节点node一直找到头节点头节点的father为null返回nullreturn node;}}}
