⼆叉树算法（python）+测试⽤例  1# 定义节点
2class TreeNode:
3def__init__(self, x):
4        self.val = x
5        self.left = None
6        self.right = None
7
8# 前序遍历（递归）
9def preorder_rec(root):
10    res = []
11if not root:
12return
13#print(root.val)
14    res.append(root.val)
15if root.left:
16        d(preorder_rec(root.left))
17if root.right:
18        d(preorder_rec(root.right))
19return res
20
21# 前序遍历（迭代）
22def preorder_iter(root):
23if not root:
24return
25    stack = [root]
26    res = []
27while stack:
28        s = stack.pop()
29if s:
30# print(s.val)
31            res.append(s.val)
32            stack.append(s.right)
33            stack.append(s.left)
34return res
35
36# 中序遍历（递归）
37def inorder_rec(root):
38if not root:
39return
40    res = []
41if root.left:
42        d(inorder_rec(root.left))
43    res.append(root.val)
44if root.right:
45        d(inorder_rec(root.right))
46return res
47
48# 中序遍历（迭代）
49def inorder_iter(root):
50if not root:
51return
52    stack = []
53    res = []
54while stack or root:
55while root:
56            stack.append(root)
57            root = root.left
58        root = stack.pop()
59        res.append(root.val)
60        root = root.right
61return res
62
63# 后序遍历（递归）
64def postorder_rec(root):
65if not root:
66return
67    res = []
68if root.left:
69        d(postorder_rec(root.left))
70if root.right:
71        d(postorder_rec(root.right))
二叉树的遍历python72    res.append(root.val)
73return res
74
75# 后序遍历（迭代）
76def postorder_iter(root):
77if not root:
78return
79    stack = []
80    res = []
81while stack or root:
82while root:
83            stack.append(root)
84if root.left:
85                root = root.left
86else:
87                root = root.right
88        s = stack.pop()
89        res.append(s.val)
90if stack and s == stack[-1].left:
91            root = stack[-1].right
92else:
93            root = None
94return res
95
96# 层序遍历
97def BFS(root):
98if not root:
99return
100    queue = [root]
101    res = []
102while queue:
103        q_len = len(queue)
104for i in range(q_len):
105            q = queue.pop(0)
106if q:
107                res.append(q.val)
108                queue.append(q.left if q.left else None)
109                queue.append(q.right if q.right else None)
110return res
111
112# ⼆叉树最⼤深度（递归）
113def max_depth_rec(root):
114if not root:
115return 0
116    l = 1 + max_depth_rec(root.left)
117    r = 1 + max_depth_rec(root.right)
118return max(l, r)
119
120# ⼆叉树最⼤深度（迭代）
121def max_depth_iter(root):
122if not root:
123return
124    stack = []
125if root:
126        stack.append((1, root))
127    depth = 0
128while stack:
129        cur_depth, root = stack.pop()
130if root:
131            depth = cur_depth if cur_depth > depth else depth
132            stack.append((cur_depth+1, root.left))
133            stack.append((cur_depth+1, root.right))
134return depth
135
136# ⼆叉树最⼩深度（递归）
137def min_depth_rec(root):
138if not root:
139return 0
140if not root.left and not root.right:
141return 1
142if root.left and not root.right:
143return 1 + min_depth_rec(root.left)
144if not root.left and root.right:
145return 1 + min_depth_rec(root.right)
146else:
147return 1 + min(min_depth_rec(root.left), min_depth_rec(root.right)) 148
149# ⼆叉树最⼩深度（迭代）
150def min_depth_iter(root):
151if not root:
152return 0
153if not root.left and not root.right:
154return 1
155    queue = [(1, root)]
156while queue:
157        cur_depth, root = queue.pop(0)
158if root.left == None and root.right == None:
159return cur_depth
160if root.left:
161            queue.append((cur_depth + 1, root.left))
162if root.right:
163            queue.append((cur_depth + 1, root.right))
164
165# ⼆叉树的所有路径
166def traverse(root):
167if not root:
168return
169if not root.left and not root.right:
170return [str(root.val)]
171    left, right = [], []
172if root.left:
173        left = [str(root.val) + x for x in traverse(root.left)] 174if root.right:
175        right = [str(root.val) + x for x in traverse(root.right)] 176return left + right
177
178if__name__ == '__main__':
179    nodelist = [TreeNode(i) for i in [4, 2, 7, 8, 3]]
180    nodelist[0].left = nodelist[1]
181    nodelist[0].right = nodelist[2]
182    nodelist[1].left = nodelist[3]
183    nodelist[1].right = nodelist[4]
184    root = nodelist[0]
185#print('⼆叉树根节点为：', root)
186print('前序遍历_递归:', preorder_rec(root))
187print('前序遍历_迭代:', preorder_iter(root))
188print('中序遍历_递归:', inorder_rec(root))
189print('中序遍历_迭代:', inorder_iter(root))
190print('后序遍历_递归:', postorder_rec(root))
191print('后序遍历_迭代:', postorder_iter(root))
192print('层次遍历:', BFS(root))
193print('最⼤深度_递归:', max_depth_rec(root))
194print('最⼤深度_迭代:', max_depth_iter(root))
195print('最⼩深度_递归:', min_depth_rec(root))
196print('最⼩深度_迭代:', min_depth_iter(root))
197print('所有路径:', traverse(root))

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。