二叉树：leetcode 236 二叉树的最近公共祖先

Jan 3, 2020 · 1 min read · Golang 二叉树 ·

本文讲解了二叉树最近公共祖先的最优算法以及背后的递归思想。

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

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

示例1：

Figure 1. 二叉树的最近公共祖先示例图

1输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
2输出: 3
3解释: 节点 5 和节点 1 的最近公共祖先是节点 3

示例2：

1输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
2输出: 5
3解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身

提示：

所有节点的值都是唯一的。
\(p、q\) 为不同节点且均存在于给定的二叉树中。

解法：

 1type TreeNode struct {
 2  Val int
 3  Left *TreeNode
 4  Right *TreeNode
 5}
 6
 7func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
 8  if root == nil{
 9    return nil	
10  }
11  if root.Val == p.Val || root.Val == q.Val{
12    return root
13  }
14  left := lowestCommonAncestor(root.Left,p,q)
15  right := lowestCommonAncestor(root.Right,p,q)
16  if left != nil && right != nil{
17    return root
18  }
19  if left == nil{
20    return right
21  }
22  return left
23}

翻译:

"English" |