参考网页： https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html
二叉树的定义
我们将Linked Data Structure的结构拓展，使得一个节点可以和两个node相连接。二叉树的结构由节点构成，有左节点和右节点并且和它本身的值。最顶层的node被称为根root
每一个node（包括root在内）都只和另一个node相连，它们之间的连接成为edge，而该node被称为parent。另一方面来讲，一个node可以和任意多个node相连，每一个node都是他的children（就是在说一个node可以有多个children但是只能有一个parent），没有children的node被称作leaves， 处在中间的node都叫内部节点，拥有相同parent的node被称为siblings.
二叉树的遍历
前序遍历 preorder
遍历顺序是：parent-left-right
给定Binary Tree， 求前序遍历得到的数值
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#Recursive
def preorder(self, root):
ans = []
self.helper(root, ans)
return ans
def helper(self, root, ans):
if root:
ans.append(root.val)
self.helper(root.left, ans)
self.helper(root.right, ans)
# Iterative
stack = []
ans = []
while root or len(stack) > 0:
while root:
ans.append(root.val)
stack.append(root.right)
root = root.left
root = stack.pop()
return ans
中序遍历 inorder
遍历顺序是：left-parent-left
给定Binary Tree， 求中序遍历得到的数值
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# Recursive
def inorder(self, root):
ans = []
self.helper(root, ans)
return ans
def helper(self, root, ans):
if root:
self.helper(root.left)
ans.append(root.val)
self.helper(root.right)
# Iteration
def inorder(self, root):
ans, stack = [], []
while root or len(stack) > 0:
while root:
stack.append(root)
root = root.left
root = stack.pop()
ans.append(root.val)
root = root.right
return ans
后序遍历 postorder
遍历顺序是：left-right-parent
给定Binary Tree，求后序遍历输出的数列
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# Recursive
def postorder(self, root):
ans = []
return self.helper(self, root, ans)
def helper(self, root, ans):
if root:
self.helper(root.left)
self.helper(root.right)
ans.append(root.val)
# Iterative
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans, stack = [], [root]
while len(stack) > 0 and root:
root = stack.pop()
ans.append(root.val)
if root.left:
stack.append(root.left)
if root.right:
stack.append(root.right)
return ans[::-1]