Sui Xin's Blog

[LeetCode]236. 二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree）

Posted on In Disqus:

题目描述

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

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

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

示例 2:

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

说明:

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

解题思路

  1. 方法一：递归。采用后序遍历，并同时判断当前节点是否为 p 或者 q，若当前节点的左、右、中三个布尔值有一个为真，则该节点的布尔值赋为真；若当前节点的左、右、中三个布尔值有至少两个为真，则说明该节点为最近公共祖先。
  2. 方法二：使用父指针迭代。迭代地将节点的父节点添加到字典中，再往上追溯 p 的父节点一直到跟节点将这些节点保存下来，最后追溯 q 的父节点，若与 p 的父节点集合重复，则其为最近公共祖先。

代码

Python 3.6

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.ans = None

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def recurse_tree(root):
            if root is None:
                return False
            left = recurse_tree(root.left)
            right = recurse_tree(root.right)
            mid = (root == p or root == q)
            if left + right + mid >= 2:
                self.ans = root
            return mid or left or right
        recurse_tree(root)
        return self.ans

执行用时: 116 ms
内存消耗: 26.9 MB

方法二：使用父指针迭代

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        stack = [root]
        parent = {root: None}
        while p not in parent or q not in parent:
            node = stack.pop()
            if node.left is not None:
                parent[node.left] = node
                stack.append(node.left)
            if node.right is not None:
                parent[node.right] = node
                stack.append(node.right)
        ancestor = []
        while p is not None:
            ancestor.append(p)
            p = parent[p]
        while q not in ancestor:
            q = parent[q]
        return q

执行用时: 100 ms
内存消耗: 17.3 MB

Related Posts