玩轉演算法面試LeetCode演算法練習——棧與遞迴(二叉樹前中後序遍歷)

NO IMAGE

目錄

 

144. 二叉樹的前序遍歷

 94. 二叉樹的中序遍歷

145. 二叉樹的後序遍歷


144. 二叉樹的前序遍歷

給定一個二叉樹,返回它的 前序 遍歷。

 示例:


輸入: [1,null,2,3]  
1
\
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.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
輸出: [1,3,2]

進階: 遞迴演算法很簡單,你可以通過迭代演算法完成嗎?


# 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 
輸出: [3,2,1]

進階: 遞迴演算法很簡單,你可以通過迭代演算法完成嗎?


# 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