所谓后继节点就是该节点的下一个遍历的节点。比如某个树的中序遍历为：3，2，1，5，4。那么1的后继节点就是5，前驱节点就是2。我们这里使用中序遍历。

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

思路

中序遍历是按照左子节点->节点->右子节点打印的，所以，当给定一个节点的时候，我们可以知道这样一个规律:

• 如果该节点有右子树，那么其后继节点一定是其右子树最左边的节点
• 如果该节点右子节点为空，那么就往父节点处搜索，并且更新，直到父节点为左子节点的时候为止，该父节点就是其后继节点。

相同的，前序，的思路大致相同就不多说了。

代码

public static Node getSuccessorNode(Node node) {if (node == null) {return node;}if (node.right != null) {return getLeftMost(node.right);} else { // 无右子树Node parent = node.parent;while (parent != null && parent.right == node) { // 当前节点是其父亲节点右孩子node = parent;parent = node.parent;}return parent;}
}public static Node getLeftMost(Node node) {if (node == null) {return node;}while (node.left != null) {node = node.left;}return node;
}