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

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

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]
}