【力扣打卡系列】二叉树的最近公共祖先

坚持按题型打卡&刷&梳理力扣算法题系列，语言为go，Day18

二叉树的最近公共祖先

• 题目描述
  
• 解题思路
  • 最近公共祖先
  • 分类讨论
    • 当前节点是空节点（返回当前节点）
    • 当前节点是p（返回当前节点）
    • 当前节点是q（返回当前节点）
    • 其他：是否找到p或q
      • 左右子树都找到（返回当前节点）
      • 只有左子树找到（返回递归左子树的结果）
      • 只有右子树找到（返回递归右子树的结果）
      • 左右子树都没有找到（返回空节点）
• 代码参考

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q{
        return root
    }
    left := lowestCommonAncestor(root.Left,p,q)
    right := lowestCommonAncestor(root.Right,p,q)
    if left != nil && right != nil{
        return root
    }
    if left != nil{
        return left
    }else{
        return right
    }
}

• tips
  • 注意go中的false条件不能省略写，一定要写成==nil的形式来判断

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

• 题目描述
  
• 解题思路
  • 可以剪枝
  • 题目保证p和q都在树中，根节点肯定不是空节点，所以不需要判断当前节点是空节点的情况
  • 分类讨论yyds！（见下图）
    
• 代码参考

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if q.Val<root.Val && p.Val<root.Val{
        return lowestCommonAncestor(root.Left,p,q)
    }else if q.Val>root.Val && p.Val>root.Val{
        return lowestCommonAncestor(root.Right,p,q)
    }else{
        return root
    }
    if root == p || root == q{
        return root
    } 
    return root
}