0%

LeetCode145 | 二叉树的后序遍历

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


每天分享一个LeetCode题目,从简单到难,每天 5 分钟,一起进步

LeetCode 后续遍历,地址:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

树结点类

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
8
9
10
11
def postorderTraversal(self, root):
def post_order(root):
if not root:
return
post_order(root.left)
post_order(root.right)
res.append(root.val)

res = []
post_order(root)
return res

非递归遍历

二叉树的后续非递归遍历,主要还是用到了栈,这里说一种比较简单的方法

这里用到了两个栈,听起来两个栈会很复杂,其实真的并没有,只要简单的画画图,就会感觉问题神奇的被解决了

1.初始化 2 个栈 s1 和 s2,并且初始化根结点到 s1 中。

2.将 s1 中栈顶元素弹出,在 s2 中压栈,并判断该元素是否有左右孩子,如果有则依次入栈 s1。否则,继续从 s1 中弹出,循环执行。

3.最后将 s2 中元素依次弹出

【后续遍历的长图】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def postorderTraversal_no_recursion(self, root):
res = []
if not root:
return res
s1, s2 = [], []
s1.append(root)
while s1:
T = s1.pop()
s2.append(T)
if T.left:
s1.append(T.left)
if T.right:
s1.append(T.right)
while s2:
res.append(s2.pop().val)
return res

完整代码

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
# -*- coding:utf-8 -*-
# !/usr/bin/env python

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

class Solution(object):
def postorderTraversal(self, root):
def post_order(root):
if not root:
return
post_order(root.left)
post_order(root.right)
res.append(root.val)

res = []
post_order(root)
return res

def postorderTraversal_no_recursion(self, root):
res = []
if not root:
return res
s1, s2 = [], []
s1.append(root)
while s1:
T = s1.pop()
s2.append(T)
if T.left:
s1.append(T.left)
if T.right:
s1.append(T.right)
while s2:
res.append(s2.pop().val)
return res


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')
# 构建二叉树
# A
# / \
# B C
# / \ / \
# D E F G
# / \
# H I
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

s = Solution()
print(s.postorderTraversal(root))
print(s.postorderTraversal_no_recursion(root))

最后

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

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