题目
现在有一种新的二叉树节点类型如下：
public class Node { public int value; public Node left; public Node right; public Node parent; public Node(int data) { this.value = data; } } 复制代码
该结构比普通二叉树节点结构多了一个指向父节点的parent指针。
假设有一棵Node类型的节点组成的二叉树， 树中每个节点的parent指针都正确地指向自己的父节点， 头节点的parent指向null。
只给一个在二叉树中的某个节点 node， 请实现返回node的后继节点的函数。
在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。
分析
对二叉树中序遍历后得到的序列存储了所有节点，在这个序列中可以找到每个节点的后继节点，用这种方式得到节点的后继节点代价比较大，因为要遍历所有的节点，时间复杂度是O(N)。
但是我们可以发现，如果任何一个节点都有一个指向父元素的指针，找节点（假设为X）的后继节点（假设为Y），时间复杂度是可以控制在O(k)的，k是X节点到Y节点的真实距离。
现在要找节点X的后继节点Y，有两种情况：
- X有右树时，Y处于X右树上的最左节点
- X无右树时，从X节点往上找，看X是不是它的左孩子，如果X是它的左孩子，那么这个节点就是X的后继节点，否则就继续往上找
另外，有一种特殊情况也要考虑：整颗树的最右节点是没有后继节点的。
public static Node getSuccessorode(Node node){ if(node == null){ return node; } if(node.right != null){ return getLeftMost(node.right); }else{ // 无右子树，往上找 Node parent = node.parent; while(parent != null && parent.left != 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; } 复制代码
相关Leetcode题
510. 二叉搜索树中的中序后继 II
这道题就是上述问题，不多讲，下面给出Javascript版本的代码：
var inorderSuccessor = function(node) { if(!node) return node; if(node.right){ // 有右孩子，找右孩子的最左节点 return getLeftMost(node.right) } // 无右孩子，往上找到一个节点，目标节点是它的左孩子 let parent = node.parent; while(parent && parent.left != node){ node = parent; parent = parent.parent; } return parent }; var getLeftMost = function(node){ if(!node) return node; while(node.left){ node = node.left; } return node; } 复制代码
面试题 04.06. 后继者
这题的不同点在于：
- 没有指向parent的指针
- 这里是二叉搜索树
法1：中序遍历
前面说过，对二叉树中序遍历后得到的序列存储了所有节点，在这个序列中可以找到每个节点的后继节点，用这种方式得到节点的后继节点代价比较大，因为要遍历所有的节点，时间复杂度是O(N)。是否可以优化呢？
可以的。由于只需要找到节点p的后继节点，因此不需要维护完整的中序遍历序列，只需要在中序遍历的过程中维护上一个访问的节点和当前访问的节点。如果上一个访问的节点是节点p，则当前访问的节点即为节点p的后继节点。
时间复杂度与空间复杂度均为O(n)
var inorderSuccessor = function(root, p) { const stack = []; let prev = null, cur = root; while(stack.length || cur){ while(cur){ stack.push(cur); cur = cur.left; } cur = stack.pop(); if(prev === p){ return cur } prev = cur; cur = cur.right } return null }; 复制代码
法2：利用二叉搜索树的性质优化搜索方向（非递归）
时间复杂度为O(n)，空间复杂度为O(1)
二叉搜索树在中序遍历后得到的序列是单调递增的，因此二叉搜索树中的节点 p 的后继节点满足条件：后继节点的节点值大于 p 的节点值。
思路
从根节点开始遍历，会遇到两种情况：
- 当前节点值大于p值，后继节点可能是该节点，也有可能是处于该节点的左子树上
- 当前节点值小于或等于p值，后继节点在该节点的右子树上
var inorderSuccessor = function(root, p) { let cur = root; let res = null; while(cur){ if(cur.val > p.val){ // 该节点值大于p值，后继节点可能是该节点，也有可能是处于该节点的左子树上 res = cur; cur = cur.left; }else{ // 该节点值小于或等于p值，后继节点在该节点的右子树上 cur = cur.right; } } return res }; 复制代码
法3：利用二叉搜索树的性质+递归
在法2的思路上，我们将其改成递归版本的。时间复杂度为O(n)，空间复杂度为O(1)
var inorderSuccessor = function(root, p) { if(!root) return null; if(root.val <= p.val) return inorderSuccessor(root.right, p); return inorderSuccessor(root.left, p) || root }; 复制代码
相关题目
总结
二叉搜索树的题目要么是根据其性质，要么考察中序遍历
