二叉树算法（python）+测试用例

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