144. 二叉樹的前序遍歷

94. 二叉樹的中序遍歷

145. 二叉樹的後序遍歷

# 144. 二叉樹的前序遍歷

示例:

``````

1
\
2
/
3

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def __init__(self):
self.ret = []
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root != None:
self.ret.append(root.val)
self.preorderTraversal(root.left)
self.preorderTraversal(root.right)
return self.ret``````

非遞迴方法：

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
result = list()
if root == None:
return result
stack = list()
stack.append(root)
while stack:
result.append(root.val)
if root.right:
stack.append(root.right)
if root.left:
stack.append(root.left)
root = stack.pop()
return result``````

# 94. 二叉樹的中序遍歷

```輸入: [1,null,2,3]
1
\
2
/
3

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def __init__(self):
self.res = []
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root != None:
self.inorderTraversal(root.left)
self.res.append(root.val)
self.inorderTraversal(root.right)
return self.res``````

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
result = list()
if root == None:
return result
stack = list()
pos = root
while stack or pos:
if pos:
stack.append(pos)
pos = pos.left
else:
pos = stack.pop()
result.append(pos.val)
pos = pos.right
return result``````

# 145. 二叉樹的後序遍歷

```輸入: [1,null,2,3]
1
\
2
/
3

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def __init__(self):
self.res = []
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root:
self.postorderTraversal(root.left)
self.postorderTraversal(root.right)
self.res.append(root.val)
return self.res``````

非遞迴：

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# 後序列印二叉樹（非遞迴）
# 使用兩個棧結構。第二個棧用來儲存列印順序，第一個棧遍歷
# 第一個棧進出棧順序：根節點（進）->根節點（出）->左節點（進）->右節點（進）->右節點（出）->左節點（出）
# 第二個棧：根節點->右節點->左節點
# 最後第二個棧依次出棧：先列印左右節點，再列印自身節點
res = []
if root == None:
return res
stack = []
stack.append(root)
stack2 = []
while stack:
root = stack.pop()
stack2.append(root)
if root.left:
stack.append(root.left)
if root.right:
stack.append(root.right)
while stack2:
res.append(stack2.pop().val)
return res``````