104. Maximum Depth of Binary Tree

Problem

Bài toán yêu cầu tìm độ sâu lớn nhất của một binary tree, tức là số lượng node trên đường đi dài nhất từ node root đến node leaf là xa nhất. Có nhiều cách để giải bài tập này, phổ biến là dùng DFS, hoặc dùng stack/queue (DFS/BFS dạng iterative)

Approach - DFS

Nếu node hiện tại là null, return 0 (cây rỗng có depth là 0)

Nếu không, độ sâu của node hiện tại sẽ là 1 (chính nó) cộng với độ sâu lớn nhất của hai cây trong trái và phải

Time and space complexity

TC: O(n), với n là số node của cây

SC: O(h), với h là chiều cao cây (do call stack đệ quy)

Solution - DFS

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 maxDepth(root: TreeNode | null): number {
16    if (!root) return 0;
17    const left_depth = maxDepth(root.left);
18    const right_depth = maxDepth(root.right);
19    return Math.max(left_depth, right_depth) + 1
20};

Approach - BFS

Sử dụng một queue đẻ duyệt từng tầng của cây

Mỗi lần hết một vòng lặp (duyệt hết một tầng), tăng biến đếm depth lên 1

Time and space complexity

TC: O(n)

SC: O(n), (do phải lưu toàn bộ node ở một tầng)

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 maxDepth(root: TreeNode | null): number {
16    if (!root) return 0;
17   
18	  let depth = 0;
19	  let queue: (TreeNode | null)[] = [root];
20	  
21	  while(queue.length > 0) {
22		  let level_size = queue.length;
23		  for(let i = 0; i < level_size; i++) {
24			  const node = queue.shift()!;
25			  if(node.left) queue.push(node.left)
26			  if(node.right) queue.push(node.right)
27		  }
28		  depth++
29	  }
30	  
31	  return depth
32};

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 maxDepth(root: TreeNode | null): number { 16 if (!root) return 0; 17 const left_depth = maxDepth(root.left); 18 const right_depth = maxDepth(root.right); 19 return Math.max(left_depth, right_depth) + 1 20};

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 maxDepth(root: TreeNode | null): number { 16 if (!root) return 0; 17 18 let depth = 0; 19 let queue: (TreeNode | null)[] = [root]; 20 21 while(queue.length > 0) { 22 let level_size = queue.length; 23 for(let i = 0; i < level_size; i++) { 24 const node = queue.shift()!; 25 if(node.left) queue.push(node.left) 26 if(node.right) queue.push(node.right) 27 } 28 depth++ 29 } 30 31 return depth 32};