235. Lowest Common Ancestor of a Binary Search Tree

Problem

Bài toán yêu cầu tìm tổ tiên chung thấp nhất (Lowest common ancestor - LCA) của hai node p và q trong một BST. LCA là node thấp nhất trong cây mà cả p và q đều là hậu duệ (có thể tính cả chính nó)

Approach -

Nhờ vào tính chất của BST: với mỗi node, các node bên trái đều nhỏ hơn các node hiện tại, các node bên phải đều lớn hơn node hiện tại

Khi duyệt từ root:

Nếu cả p và q đều nhỏ hơn node hiện tại, LCA nằm ở bên trái

Nếu cả p và q đều lớn hơn node hiện tại. LCA nằm ở bên phải

Nếu cả p và q nằm hai phía khác nhau (một nhỏ hơn, một lớn hơn hoặc bằng một node hiện tại), node hiện tại chính là LCA

Time and space complexity

TC: O(n)

SC: O(1)

Solution

typescripttypescript

1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 *     val: number
5 *     left: TreeNode | null
6 *     right: TreeNode | null
7 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 *         this.val = (val===undefined ? 0 : val)
9 *         this.left = (left===undefined ? null : left)
10 *         this.right = (right===undefined ? null : right)
11 *     }
12 * }
13 */
14
15function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
16	while(root) {
17		if(root.val > p.val && root.val > q.val) {
18			root = root.left;
19		} else if(root.val < p.val && root.val < q.val) {
20			root = root.right
21		} else {
22			return root
23		}
24	}
25	return null;
26};

💡

Giải thích ngắn gọn

Tận dụng tính chất BST để rẽ nhánh tìm LCA

Dừng lại khi p và q nằm hai phía khác nhau hoặc bằng node hiện tại

Loading content...

235. Lowest Common Ancestor of a Binary Search Tree

Related Posts

Related Posts

235. Lowest Common Ancestor of a Binary Search Tree

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists