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

二叉树#

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

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

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

1
输入：root = [1,2], p = 1, q = 2
2
输出：1

递归的解法

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
10
    if root == nil || root == p || root == q {
11
        return root
12
    }
13

14
    left := lowestCommonAncestor(root.Left, p, q)
15
    right := lowestCommonAncestor(root.Right, p, q)
16

17
    if left != nil && right != nil {
18
        return root
19
    }else if left != nil && right == nil {
20
        return left
21
    }else if left == nil && right != nil {
22
        return right
23
    }else {
24
        return nil
25
    }
26
}