0%

leetcode104 | 二叉树的最大深度

读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw


每天分享一个LeetCode题目

每天 5 分钟,一起进步

LeetCode104 二叉树的最大深度,地址: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

树结点定义

1
2
3
4
5
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

递归方式

递归方式比较简单,就是一个后续遍历,然后在遍历到根结点的时候进行左右比较,选择大的孩子

1
2
3
4
5
6
7
def maxDepth_dfs(self, root):
if not root:
return 0
else:
max_left = self.maxDepth_dfs(root.left)
max_right = self.maxDepth_dfs(root.right)
return max(max_left, max_right) + 1

看,是不是一个很简单的后续遍历,就是最后选择大的分支

但是非递归的方式对于很多从上到下的遍历也很适用,而且简单

非递归方式

LeetCode 102 二叉树的层序遍历 以及 LeetCode 107 N叉树层序遍历 的思路一致,就是一个层序遍历的过程

初始化一个 node_depth = 0,然后遍历到每一层的时候进行 node_depth + 1,最后返回 node_depth

看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maxDepth_bfs(self, root):
if not root:
return 0
queue = collections.deque()
# 初始化深度为 0
node_depth = 0
# 初始化队列中的结点元素 root
queue.appendleft(root)
while queue:
# 每一层的遍历,深度 +1
node_depth += 1
# 记录每一层的结点集合
tmp_queue = []
for node in queue:
if node.left:
tmp_queue.append(node.left)
if node.right:
tmp_queue.append(node.right)
queue = tmp_queue

return node_depth

尤其是很多地方都会使用像这种 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# -*- coding:utf-8 -*-
# !/usr/bin/env python

import collections

# 树结点类
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right


class Solution(object):
def maxDepth_dfs(self, root):
if not root:
return 0
else:
max_left = self.maxDepth_dfs(root.left)
max_right = self.maxDepth_dfs(root.right)
return max(max_left, max_right) + 1

def maxDepth_bfs(self, root):
if not root:
return 0
queue = collections.deque()
# 初始化深度为 0
node_depth = 0
# 初始化队列中的结点元素 root
queue.appendleft(root)
while queue:
# 每一层的遍历,深度 +1
node_depth += 1
# 记录每一层的结点集合
tmp_queue = []
for node in queue:
if node.left:
tmp_queue.append(node.left)
if node.right:
tmp_queue.append(node.right)
queue = tmp_queue

return node_depth


if __name__ == "__main__":
# 新建节点
root = TreeNode('A')
node_B = TreeNode('B')
node_C = TreeNode('C')
node_D = TreeNode('D')
node_E = TreeNode('E')
node_F = TreeNode('F')
node_G = TreeNode('G')
node_H = TreeNode('H')
node_I = TreeNode('I')
node_J = TreeNode('J')
# 构建二叉树
# A
# / \
# B C
# / \ / \
# D E F G
# / \
# H I
# \
# J
root.left, root.right = node_B, node_C
node_B.left, node_B.right = node_D, node_E
node_C.left, node_C.right = node_F, node_G
node_D.left, node_D.right = node_H, node_I
node_I.right = node_J

s = Solution()
print(s.maxDepth_dfs(root))
print(s.maxDepth_bfs(root))

Github

https://github.com/xiaozhutec/PyCode

最后

在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取
有任何问题,欢迎随时交流!!!

------ 全文结束------