给你二叉树中的某个结点，返回该结点的后继结点

二叉树结构定义如下&＃xff1a;

public static class Node {public int value;public Node left;public Node right;public Node parent;public Node(int data) {this.value &＃61; data;}}

后继结点&＃xff1a;在一棵二叉树中&＃xff0c;在中序遍历中&＃xff0c;一个结点的下一个结点是谁&＃xff01;

大多数人普遍能想到的办法是&＃xff0c;借助该结点往父结点指的指针&＃xff0c;找到头结点&＃xff0c;然后再中序遍历整棵树&＃xff0c;然后找到后继结点。但是此种方法时间复杂度必然是O(N)。因为遍历二叉树本质是递归序。所以&＃xff0c;有没有办法可以不用遍历二叉树&＃xff0c;后继结点离给定的结点距离为K的话&＃xff0c;可以直接找到呢&＃xff1f;如果可以&＃xff0c;那么时间复杂度就是O(K&＃xff09;。

我们都知道&＃xff0c;中序遍历顺序是左根右&＃xff0c;所以如果一个结点有右树的话&＃xff0c;该结点的后继结点必然是该结点右树上最左的结点

所以同理&＃xff0c;我们可以认识知道&＃xff0c;前驱结点&＃xff08;在一棵二叉树中&＃xff0c;在中序遍历中&＃xff0c;一个结点的前一个结点是谁&＃xff09;&＃xff1a;如果一个结点有左树的话&＃xff0c;该结点的前驱结点就是该结点左树上最右的结点。当然&＃xff0c;本篇文章我们只讨论后继结点的问题。

那么如果这个结点没右孩子呢&＃xff1f;&＃xff0c;这种情况它的后继结点怎么找呢&＃xff1f;

x结点的后继节点&＃xff1a;某一个结点&＃xff08;用?代替&＃xff09;的整颗左树上的最右结点是x&＃xff0c;则&＃xff1f;就是x的后继结点&＃xff0c;但是整棵树的最右结点没有后继。 x就是&＃xff1f;的前驱结点

附上截图&＃xff0c;方便大家理解

package com.harrison.class07;public class Code07_SuccessorNode {public static class Node {public int value;public Node left;public Node right;public Node parent;public Node(int data) {this.value &＃61; data;}}public static Node getSuccessorNode(Node node) {if(node&＃61;&＃61;null) {return node; }if(node.right!&＃61;null) {// 给定的结点有右孩子return getLeftMost(node.right);}else {// 给定的结点无右孩子Node parent&＃61;node.parent;while(parent!&＃61;null && parent.right&＃61;&＃61;node) {// 当前结点不是父结点的左孩子node&＃61;parent;parent&＃61;node.parent;}return parent;}}public static Node getLeftMost(Node node) {if(node&＃61;&＃61;null) {return node; }while(node.left!&＃61;null) {node&＃61;node.left;}return node;}public static void main(String[] args) {Node head &＃61; new Node(6);head.parent &＃61; null;head.left &＃61; new Node(3);head.left.parent &＃61; head;head.left.left &＃61; new Node(1);head.left.left.parent &＃61; head.left;head.left.left.right &＃61; new Node(2);head.left.left.right.parent &＃61; head.left.left;head.left.right &＃61; new Node(4);head.left.right.parent &＃61; head.left;head.left.right.right &＃61; new Node(5);head.left.right.right.parent &＃61; head.left.right;head.right &＃61; new Node(9);head.right.parent &＃61; head;head.right.left &＃61; new Node(8);head.right.left.parent &＃61; head.right;head.right.left.left &＃61; new Node(7);head.right.left.left.parent &＃61; head.right.left;head.right.right &＃61; new Node(10);head.right.right.parent &＃61; head.right;Node test &＃61; head.left.left;// 1System.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test).value);test &＃61; head.left.left.right;// 2System.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test).value);test &＃61; head.left;// 3System.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test).value);test &＃61; head.left.right;// 4System.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test).value);test &＃61; head.left.right.right;// 5System.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test).value);test &＃61; head;// 6System.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test).value);test &＃61; head.right.left.left;// 7System.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test).value);test &＃61; head.right.left;// 8System.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test).value);test &＃61; head.right;// 9System.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test).value);test &＃61; head.right.right; // 10&＃39;s next is nullSystem.out.println(test.value &＃43; " next: " &＃43; getSuccessorNode(test));}
}