读前福利：几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw
每天分享一个LeetCode题目
每天 5 分钟，一起进步!
LeetCode 中序遍历，地址：https://leetcode-cn.com/problems/binary-tree-inorder-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 inorderTraversal(self, root):
def in_order(root):
if not root:
return
in_order(root.left)
res.append(root.val)
in_order(root.right)
res = []
in_order(root)
return res
|
非递归遍历
非递归遍历，也是要借助【栈】来进行实现的
1.不断访问左孩子，压栈，直到被访问的左孩子为空
2.从栈顶弹出结点并且访问，随后访问右孩子，如果右孩子为空，则从栈顶弹出结点并且访问。否则，继续执行第 1 点
3.直到栈为空并且被访问的右孩子也为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def inorderTraversal_no_recursion(self, root):
if not root:
return []
stack = []
res = []
while stack or root:
while root:
stack.append(root)
root = root.left
if stack:
tmp = stack.pop()
res.append(tmp.val)
root = tmp.right
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
|
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def inorderTraversal(self, root):
def in_order(root):
if not root:
return
in_order(root.left)
res.append(root.val)
in_order(root.right)
res = []
in_order(root)
return res
def inorderTraversal_no_recursion(self, root):
if not root:
return []
stack = []
res = []
while stack or root:
while root:
stack.append(root)
root = root.left
if stack:
tmp = stack.pop()
res.append(tmp.val)
root = tmp.right
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')
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.inorderTraversal(root))
print(s.inorderTraversal_no_recursion(root))
|
最后
在这里给大家准备了几百本的互联网技术类书籍，需要的来下载吧！点击获取
有任何问题，欢迎随时交流!!!
