1.题目
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回null。
2.示例
示例 1:
输入: root = [2,1,3], p = 1
2 / \ 1 3
输出: 2
示例 2:
输入: root = [5,3,6,2,4,null,null,1], p = 6
5 / \ 3 6 / \ 2 4 / 1
输出: null
3.思路
要找到二叉树的下一个节点，所以要把走过的节点存下来，才知道节点和节点之间的先后关系。因为某一结点的下一个节点很可能并不和当前节点相邻，只要明白二叉树的组成原理应该不用多说。根据二叉搜索树的组成原理可以通过存下路径找出结果。
4.代码
为了思路清晰方便理解，我把遍历过程分成了两个部分
func inorderSuccessor(root, p *TreeNode) *TreeNode { //存放路径的节点切片 st := []*TreeNode{} //上一个节点和当前节点 var pre, cur *TreeNode = nil, root //只要当前路径切片不为空或者当前节点不为nil for len(st) > 0 || cur != nil { //第一部分 //只要当前节点不为空就一直向左子树遍历，直到到了最后的叶子节点 for cur != nil { st = append(st, cur) cur = cur.Left } //此时当前节点为nil,通过从路径中取最后一个节点作为当前节点 cur = st[len(st)-1] st = st[:len(st)-1] //如果上一个节点是目标节点,则当前节点就是要找的节点 if pre == p { return cur } //至此从上一个节点到最后的左子树节点遍历结束 //第二部分 //如果没有找到目标节点,则遍历当前节点的右子树 pre = cur cur = cur.Right } return nil }
