前驅(qū)節(jié)點(diǎn)：對(duì)一棵二叉樹進(jìn)行中序遍歷，遍歷后的順序，當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)；
后繼節(jié)點(diǎn)：對(duì)一棵二叉樹進(jìn)行中序遍歷，遍歷后的順序，當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)為該節(jié)點(diǎn)的后繼節(jié)點(diǎn)；
例如一顆完全二叉樹（1,2,3,4,5,6,7），按照中序遍歷后的順序?yàn)椋海?,2,5,1,6,3,7），1節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)為：5，后繼節(jié)點(diǎn)為6.
若每次遍歷二叉樹進(jìn)行查找前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)，復(fù)雜度太高，需要O(n)的時(shí)間復(fù)雜度。例如查找5節(jié)點(diǎn)的后繼節(jié)點(diǎn)，則需要對(duì)整棵樹進(jìn)行遍歷，而真正可以做到的是，只需要經(jīng)過兩者之間的距離就可以找到其后繼節(jié)點(diǎn)：52
1。
因此可以斷定：
前驅(qū)節(jié)點(diǎn)：當(dāng)前節(jié)點(diǎn)左子樹的最右節(jié)點(diǎn)（例如1節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)為5），若無左子樹，則：當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子樹（5節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)為2）；
后繼節(jié)點(diǎn)：當(dāng)前節(jié)點(diǎn)右子樹的最左節(jié)點(diǎn)（1節(jié)點(diǎn)的后繼節(jié)點(diǎn)為6），若無右子樹，則：當(dāng)前節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子樹（6節(jié)點(diǎn)的后繼節(jié)點(diǎn)為3）。
Java代碼：找后繼節(jié)點(diǎn)：
public class GetSuccessposNode {//找后繼節(jié)點(diǎn)
public static class Node{
????????int value;
????????Node parent;
????????Node leftNode;
????????Node rightNode;
????????public Node(int data) {
????????????????this.value = data;
????????}
????}
public static Node getSuccessNode(Node node) {
????????if (node == null) {
????????????????return node;
????????}
????????if (node.rightNode!=null) {
????????????????return getLeftNode(node.rightNode);
????????}else {
????????????????Node parent = node.parent;
????????????????while (parent!=null && parent.leftNode!=node) {
????????????????????????node = parent;
????????????????????????parent = node.parent;
????????????????}
????????????????return parent;
????????}
}
private static Node getLeftNode(Node node) {
????????if (node == null) {
????????????????return node;
????????}
????????while (node.leftNode!=null) {
????????????????node = node.leftNode;
????????}
????????return node;
}
}
找前驅(qū)節(jié)點(diǎn)：
public class GetSuccesspreNode {
????????public static class Node {
????????????????int value;
????????????????Node parentNode;
????????????????Node leftNode;
????????????????Node rightNode;
????????????????public Node(int data) {
????????????????????????this.value = data;
????????????????}
????????}
public static Node getSuccessPreNode(Node node) {
????????if (node==null) {
????????????????return node;
????????}
????????if (node.leftNode!=null) {
????????????????return getRightNode(node.leftNode);
????????}else {
????????????????Node parent = node.parentNode;
????????????????while (parent!=null && parent.rightNode!=node) {
????????????????????????node = parent;
????????????????????????parent = node.parentNode;
????????????????}
????????????????return node;
????????}
}
private static Node getRightNode(Node node) {
????????if (node==null) {
????????????????return node;
????????}
????????while (node.rightNode!=null) {
????????????????node = node.rightNode;
????????}
????????return node;
}
}
