golang力扣leetcode 面试题04.06.后继者

• 面试题04.06.后继者
• 题解
• 代码

面试题04.06.后继者

题目：给定一个二叉搜索树，和一个节点p，求节点p的后继节点（中序遍历的下一个节点）

思路：

利用性质
1.如果root>p，说明p在左子树，进入左子树，同时记录prev=root原来的位置
2.如果root=p,说明找到了，此时prev就是p的后继

中序遍历
1.按照左根右的顺序，递归把节点存下来
2.根据p.val二分即可

func inorderSuccessor1(root *TreeNode, p *TreeNode) *TreeNode {
	var prev *TreeNode
	for root != nil {
		if root.Val > p.Val {
			prev = root
			root = root.Left
		} else {
			root = root.Right
		}
	}
	return prev
}
func inorderSuccessor2(root *TreeNode, p *TreeNode) *TreeNode {
	order := make([]*TreeNode, 0)
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		if root.Left != nil {
			dfs(root.Left)
		}
		order = append(order, root)
		if root.Right != nil {
			dfs(root.Right)
		}
	}
	dfs(root)
	n := sort.Search(len(order), func(i int) bool {
		return order[i].Val > p.Val
	})
	if n == len(order) {
		return nil
	}
	return order[n]
}