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

坚持按题型打卡&刷&梳理力扣算法题系列，语言为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
}