題目

LeetCode - 236. Lowest Common Ancestor of a Binary Tree

解題思路

給定一個二元樹及其中兩個不同的節點，試找出它們的最近共同祖先(LCA)。

  • 注意: a node to be a descendant of itself 自己可以是自己的後裔

根據「Lowest Common Ancestor（最低共同祖先）」的定義，我們可以稍微整理出以下規則：

  • 當這兩個節點處於不同的左右子樹中時，那麼最低公共祖先節點就是這兩棵左右子樹的根節點
  • 當這兩個節點處於同一子樹中，那麼最低公共祖先節點就是這兩個節點中最低的那個節點

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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':
        if root == None or root==p or root==q: return root
        left  = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
            
        if left and right:
            return root
        
        return left if left else right

Reference