236. Lowest Common Ancestor of a Binary Tree

Problem

Bài toán yêu cầu tìm Lowest common Ancestor (LCA) của hai node p và q trong một binary tree. LCA được định nghĩa là node thấp nhất trong cây có cả p và q là hậu duệ (bao gồm trường hợp một node la hậu duệ của chính nó)

💡

“Thấp nhất” có nghĩa là node (đỉnh) tổ tiên chung của hai node p và q nằm ở vị trí gần nhất với hai node này trên cây, tức là ở (level) sâu nhất tính từ root xuống mà vẫn là tổ tiên của cả p và q

Nếu p là tổ tiên của q thì "tổ tiên chung thấp nhất" chính là p.

Nếu p và q nằm ở hai nhánh khác nhau, thì node giao nhau đầu tiên trên đường đi từ p và q lên gốc chính là tổ tiên chung thấp nhất.

“Giao nhau đầu tiên”

Để đi từ gốc đến p hoặc từ gốc đến q, bạn đều phải đi qua node này, và nếu đi sâu hơn thì chỉ còn đi đến p hoặc q riêng lẻ mà thôi, không còn node nào là tổ tiên chung nữa

Approach

Để giải bài toán này, ta sử dụng phương pháp đệ quy với các bước như sau:

Nếu node hiện tại là null, hoặc chính là p hoặc q, return node hiện tại

Đệ quy tìm kiếm LCA trong cây con bên trái và cây con bên phải

Nếu cả hai cây con đều trả về giá trị khác null. Nghĩa là p nằm trong một cây con và q nằm trong cây con còn lại. Khi đó, node hiện tại chính là LCA

Nếu chỉ một trong hai cây con trả về giá trị khác null, thì LCA nằm trong cây con đó

Time and space complexity

TC: O(n), với n là số lượng node trong binary tree

SC: O(h), với h là chiều cao của binary tree

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	if(!root || root === p || root === q) {
17		return root;
18	}
19	
20	const left = lowestCommonAncestor(root.left, p, q)
21	const right = lowestCommonAncestor(root.right, p, q)
22	
23	if(left && right) {
24		return root;
25	}
26	
27	return left || right;
28};

💡

“Quay lại” trong đệ quy?

Trong thuật toán đệ quy, lần bạn gọi một hàm, chương trình sẽ “ghi nhớ” trạng thái hiện tại (bao gồm các biến cục bộ, vị trí thực thi….) vào ngăn xếp (call stack).

Khi hàm con hoàn thành (tức là gặp lệnh return ), nó sẽ trả kết quả về cho hàm cha đã gọi nó. Quá trình này gọi là “quay lại” (return back hoặc unwind recursion)

Bạn không cần phải viết code "quay lại" vì đây là cách mà mọi hàm đệ quy (và cả hàm thông thường) hoạt động trong mọi ngôn ngữ lập trình hiện đại.

Áp dụng vào thuật toán LCA

Loading content...

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 if(!root || root === p || root === q) { 17 return root; 18 } 19 20 const left = lowestCommonAncestor(root.left, p, q) 21 const right = lowestCommonAncestor(root.right, p, q) 22 23 if(left && right) { 24 return root; 25 } 26 27 return left || right; 28};

236. Lowest Common Ancestor of a Binary Tree

Related Posts

Related Posts

236. Lowest Common Ancestor of a Binary 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