我是靠谱客的博主 高兴咖啡豆,这篇文章主要介绍leetcode: 二叉树的三种非递归遍历,现在分享给大家,希望可以做个参考。

复制代码
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
77
78
79
80
81
82
83
class TreeNode: def __init__(self,val): super(TreeNode).__init__() self.val = val self.left = None self.right = None self.isPop = False def createTree(valList): if not valList: raise ValueError("input value list is None!") root = TreeNode(valList[0]) valList.pop(0) layerOne = [root] layerTwo = [] i = 0 while i<len(valList): n = layerOne.pop(0) if valList[i] is not None: n.left = TreeNode(valList[i]) layerOne.append(n.left) i = i+1 if i<len(valList) and valList[i] is not None: n.right = TreeNode(valList[i]) layerOne.append(n.right) i = i+1 return root valList = [1,2,3,4,None,6,7,8,9,None,11,12,13] root = createTree(valList) def inOrder(root): stack = [] p = root while stack or p: if p: stack.append(p) p = p.left else: p = stack.pop() print(p.val,end = " ") p = p.right print() def preOrder(root): if not root: return stack = [root] while stack: p = stack.pop() print(p.val,end=" ") if p.right: stack.append(p.right) if p.left: stack.append(p.left) print() def postOrder(root): def operate(node,stack): if node.left is None and node.right is None or node.isPop: print(node.val,end=" ") else: stack.append(node) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return stack if not root: return stack = [root] while stack: p = stack.pop() stack=operate(p,stack) p.isPop = True preOrder(root) #1 2 4 8 9 3 6 11 7 12 13 inOrder(root) #8 4 9 2 1 6 11 3 12 7 13 postOrder(root) #8 9 4 2 11 6 12 13 7 3 1

后序遍历的实现方法中,改变节点的入栈顺序也可以用来实现另外两种遍历

最后

以上就是高兴咖啡豆最近收集整理的关于leetcode: 二叉树的三种非递归遍历的全部内容,更多相关leetcode:内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(139)

评论列表共有 0 条评论

立即
投稿
返回
顶部