DFS經典應用題 BST最靠近的公共祖先節點 Leetcode #235

Hoi An Photographer on Unsplash

題目敘述

題目會給定我們一顆二元搜索樹的根結點root，和任意兩個樹中的節點p和q。

要求我們找出p, q最靠近的公共祖先節點。

最靠近的公共祖先節點 用白話講，就是p, q 分別往上走，第一個產生交會的節點。

題目的原文敘述

測試範例

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2
 

約束條件

Constraints:

• The number of nodes in the tree is in the range [2, 10^5].
• -109 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

演算法

善加利用BST的先天規定與特質:

BST本身是一個排序好的二元樹。

左子樹一定比根節點的值還小。

右子樹一定比根結點的值還大。

討論可能出現的情況:

若p, q 都比根結點小，則搜尋左子樹。

若p, q 都比根結點大，則搜尋右子樹。

若p, q一個比根結點大，另一個比根結點小，則當下的節點就是最靠近的公共祖先節點，(Lowest common ancestor, aka LCA )恰好符合定義，即為所求。

程式碼

class Solution:
　def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

　　cur_value = root.val
　　
　　if p.val > cur_value and q.val > cur_value:
　　　return self.lowestCommonAncestor( root.right, p, q)
　　
　　elif p.val < cur_value and q.val < cur_value:
　　　return self.lowestCommonAncestor( root.left, p, q)
　　
　　else:
　　　return root

關鍵知識點

記得聯想到BST二元搜索樹的先天規定與特質:

BST本身是一個排序好的二元樹。

左子樹一定比根節點的值還小。

右子樹一定比根結點的值還大。

題目的定義，往往就暗藏解題的線索唷!

Reference:

[1] Lowest Common Ancestor of a Binary Search Tree - LeetCode