二叉树算法—后继节点

与其明天开始，不如现在行动！

---

1 后继节点

1.1 解题思路

二叉树节点结构定义如下：

public static class Node {
public int cal;
public Node left;
public Node right;
public Node parent;
}
给你二叉树中的某个节点，返回该节点的后继节点

后继节点就是二叉树中序遍历，这个节点的下一个节点

思路

1. 如果该节点有右子树，那么后继节点就是右树的最左节点
2. 如果该节点没有右子树
   1. 如果该节点是父节点的左节点，此时父节点就是后继节点
   2. 如果该节点是父节点的右节点，向上寻找
      1. 这个节点在顶部节点的右树上，此时返回的是空
      2. 如果这个节点在某个节点的左数上，返回此时的节点

1.2 代码实现

public class SuccessorNode {public static class Node {public int val;public Node left;public Node right;public Node parent;public Node(int val) {this.val = val;}}public static Node getSuccessorNode(Node node) {if (node == null) {return node;}if (node.right != null) {return getLeftMost(node.right);}else{Node cur = node;Node parent = node.parent;while (parent != null && parent.left != node) {cur = parent;parent = cur.parent;}return parent;}}private static Node getLeftMost(Node node) {Node cur = node;if (cur.left != null) {cur = cur.left;}return cur;}// 测试public static void main(String[] args) {Node n1 = new Node(1);Node n2 = new Node(2);Node n3 = new Node(3);Node n4 = new Node(4);Node n5 = new Node(5);Node n6 = new Node(6);Node n7 = new Node(7);n1.left = n2;n1.right = n3;n2.left = n4;n2.right = n5;n2.parent = n1;n3.left = n6;n3.right = n7;n3.parent = n1;n4.parent = n2;n5.parent = n2;n6.parent = n3;n7.parent = n3;System.out.println(getSuccessorNode(n6).val);}
}

---

💎总结

本文中若是有出现的错误请在评论区或者私信指出，我再进行改正优化，如果文章对你有所帮助，请给博主一个宝贵的三连，感谢大家😘！！！

---