剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先

和力扣 235. 二叉搜索树的最近公共祖先 236. 二叉树的最近公共祖先一致

236. 二叉树的最近公共祖先

难度中等1243收藏分享切换为英文接收动态反馈
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
剑指 68 . 二叉树的最近公共祖先 🍳 - 图1
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5和节点 1的最近公共祖先是节点 3 。

  1. //搜索树    迭代
  2. func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  3.     for root != nil {
  4.         if p.Val < root.Val && q.Val < root.Val {
  5.             root = root.Left
  6.         } else if p.Val > root.Val && q.Val > root.Val {
  7.             root = root.Right
  8.         } else {
  9.             break
  10.         }
  11.     }
  12.     return root
  13. }
  16. //递归
  17. func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  18.     if p.Val < root.Val && q.Val < root.Val {
  19.         return lowestCommonAncestor(root.Left, p, q)
  20.     } 
  21.     if p.Val > root.Val && q.Val > root.Val {
  22.         return lowestCommonAncestor(root.Right, p, q)
  23.     }
  24.     return root
  25. }
//二叉树，只有递归，时空On，有点秀
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return root
    }

    if p.Val == root.Val || q.Val == root.Val {
        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
}