力扣二叉树--第三十九天

前言

本来打算这几天不写题了，等待是痛苦的，复习完了就写写题吧，等待考试多焦虑啊。

内容

一、二叉树的最近公共祖先

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

递归

 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if root==nil{
         return root
     }
    if 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
   }// 如果左子树和右子树都找到了最低公共祖先，那么当前节点 root 就是最低公共祖先。
   if left!=nil{
       return left
   }//如果左子树找到了最低公共祖先，那么返回左子树的最低公共祖先
  if right!=nil{
      return right
  }
  return nil
}

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

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

递归

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

最后

事情没有这么简单吧，我搜索二叉树的公共祖先，有一堆算法。。。以后再看吧。