104. Maximum Depth of Binary Tree
Tags:
Easy
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
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
Time and space complexity
Solution - DFS
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
Time and space complexity
Solution
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};