235. 二叉🌲/搜索树的最近公共祖先 👌

235. 二叉搜索树的最近公共祖先

“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

• 根据二叉搜索树性质：如果 p.val 和 q.val 都比 root.val 小，则 p、q 肯定在 root 的左子树。
• 那问题规模就变小了，递归左子树就行！
• 如果 p.val 和 q.val 都比 root.val 大，递归右子树就行！
• 其他情况，root 即为所求！那么简单吗？为什么？
  • 只要不是 p.val 和 q.val 都大于(小于) root.val，即只要 p, q 不同处在 root 的一个子树
  • 就只有这三种情况：
    • p 和 q 分居 root 的左、右子树。
    • root 就是 p，q 在 p 的子树中。
    • root 就是 q，p 在 q 的子树中
  • 而这三种情况，p 和 q 的最近公共祖先都是 root！是不是很简单！

    //递归：
    func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if p.Val < root.Val && q.Val < root.Val {
       return lowestCommonAncestor(root.Left, p, q)
    }
    if p.Val > root.Val && q.Val > root.Val {
       return lowestCommonAncestor(root.Right, p, q)
    }
    return root
    }

    //迭代
    func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    for root != nil {
       if p.Val < root.Val && q.Val < root.Val {
           root = root.Left
       } else if p.Val > root.Val && q.Val > root.Val {        //是else if； 不是if
           root = root.Right
       } else {
           break
       }
    }
    return root
    }
    

进阶版本：二叉树

思路：递归解法，优化—— 「利用哈希表存父节点，可以转换为相交链表问题」

我们想一下，对于根节点 root，p、q 的分布，有两种可能：

• p、q 分居 root 的左右子树，则 LCA 为 root。

• p、q 在 root 的同一个子树中，问题转为规模小一点的相同问题。

  定义递归函数

  递归函数：返回当前子树中 p 和 q 的 LCA。如果没有 LCA，就返回 null。
  从根root开始递归搜索，递归搜到各个子树……

• 如果遍历到 p 或 q，比方说 p，则 LCA 要么是当前的 p（q 在 p 的子树中），要么是 p 之上的节点（q 不在 p 的子树中），不可能是 p 之下的节点。不用继续往下遍历，返回当前的 p。

• 当遍历到 null 节点，空树不存在 p 和 q，不存在 LCA，返回 null。

• 当遍历的节点 root 不是 p 或 q 或 null，则递归搜寻 root 的左右子树：

  1. 如果左右子树的递归都有结果，说明 p 和 q 分居 root 的左右子树，返回 root。
  2. 如果只是一个子树递归调用有结果，说明 p 和 q 都在这个子树，返回该子树递归结果。
  3. 如果两个子树递归结果都为 null，说明 p 和 q 都不在这俩子树中，返回 null。

• 时间复杂度 O(N) ： 其中 N 为二叉树节点数；最差情况下，需要递归遍历树的所有节点。

• 空间复杂度 O(N) ： 最差情况下，递归深度达到 N ，系统使用O(N) 大小的额外空间。

  //递归 
  func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    if root == p || root == q {
        return root
    }
  
    left := lowestCommonAncestor(root.Left, p, q )
    right := lowestCommonAncestor(root.Right, p, q )
  
    if left == nil  {
        return right
    }
    if right == nil {
        return left
    }
    return root
  }
  

  复盘总结

• 应该不难想到递归解决

• 何时问题会变成一个规模小一点的同一问题，用到递归处理
• 分情况讨论，根据当前遍历的节点是谁，决定当前递归做什么事，是直接返回，还是递归

牛客网变形：修改参数类型——节点改为值

变种：给定一棵二叉树，这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

func lowestCommonAncestor( root *TreeNode ,  o1 int ,  o2 int ) int {
    if root == nil {
        return -1
    }

    node := isParent(root,o1,o2)
    if node != nil {
        return node.Val
    }
    return -1
}

func isParent(root *TreeNode, o1, o2 int) *TreeNode {
    if root == nil {
        return root
    }

    if root.Val == o1 || root.Val == o2 {
        return root
    }

    left := isParent(root.Left, o1, o2)
    right := isParent(root.Right, o1, o2)

    if left == nil {
        return right
    }
    if right == nil {
        return left
    }
    return root
}