【Leetcode】104. Maximum Depth of Binary Tree

Description

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
return its depth = 3.

DFS with Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val)
# @val = val
# @left, @right = nil, nil
# end
# end

# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
root.nil?? 0 : [max_depth(root.left), max_depth(root.right)].max + 1
end

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val)
# @val = val
# @left, @right = nil, nil
# end
# end

# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
depth = 0
tree = []

tree << root unless root.nil?

while !tree.empty?
depth += 1


n = tree.size - 1

for i in 0..n
node = tree.shift
tree << node.left unless node.left.nil?
tree << node.right unless node.right.nil?
end
end

depth
end

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val)
# @val = val
# @left, @right = nil, nil
# end
# end

# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
tree = []
res = []

unless root.nil?
tree << root
res << 1
end

max = 0
while !tree.empty?
node = tree.pop
tmp = res.pop
max = [max, tmp].max if node.right.nil? && node.left.nil?

if node.right.present?
tree << node.right
res << tmp + 1
end

if node.left.present?
tree << node.left
res << tmp + 1
end
end

max
end