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

题目链接

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

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    //  思路：后续遍历，如果当前跟节点包含了节点p,q，则为最近公共祖先
    // 如果判断当前的包含状态呢？状态压缩
    // 声明函数变量
    var fun func(root *TreeNode) int
    // 存放最近公共祖先
    var ans *TreeNode = nil
    // 后续遍历递归函数
    fun = func(root *TreeNode) int{
        // 如果根节点为空，则返回0，表示不包含p跟q
        if root == nil {
            return 0
        }
        // 统计当前root为根的子树中，包含p跟q的情况
        state := 0
        // 累加左子树的情况
        state |= fun(root.Left)
        // 累加右子树的情况
        state |= fun(root.Right)
        // 如果根节点为p，则或上1
        if root == p {
            state |= 1
        } else if root == q {
            // 如果根节点为q，则或上2
            state |= 2
        }
        // 如果ans没有被修改过 并且 以root为根的子树包含了p跟q，则更新最近公共祖先
        if ans == nil && state == 3{
            ans = root
        }
        // 返回以root为根的子树包含p跟q的情况
        return state
    }
    // 调用函数
    fun(root)
    // 返回结果
    return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46