python3 参考这篇题解:二叉树遍历https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/tu-jie-er-cha-shu-de-si-chong-bian-li-by-z1m/
前序遍历:根->左->右
LeetCode 144.二叉树的前序遍历
迭代解法:(借助栈)
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
stack, res=[root], []
while stack:
node=stack.pop()
if node:
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
递归解法:
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
def preorder(root):
nonlocal res
if not root:
return
res.append(root.val)
preorder(root.left)
preorder(root.right)
preorder(root)
return res
中序遍历:左->根->右
Leetcode 94. 二叉树的中序遍历
递归解法:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
stack, res= [(0,root)], []
while stack:
flag, node=stack.pop()
if not node: continue
if flag==1: res.append(node.val)
else:
stack.append((0,node.right))
stack.append((1,node))
stack.append((0,node.left))
return res
递归解法:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
def inorder(root):
nonlocal res
if not root:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
inorder(root)
return res
后序遍历:左->右->根
Leetcode 145. 二叉树的后序遍历
迭代解法:
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
stack, res= [(0,root)], []
while stack:
flag, node=stack.pop()
if not node: continue
if flag==1: res.append(node.val)
else:
stack.append((1,node))
stack.append((0,node.right))
stack.append((0,node.left))
return res
递归解法:
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res= []
def postorder(root):
nonlocal res
if not root:
return
postorder(root.left)
postorder(root.right)
res.append(root.val)
postorder(root)
return res
层序遍历:广度优先算法,用队列
Leetcode102. 二叉树的层序遍历
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, q= [], [root]
while q:
level=[]
n= len(q)
for i in range(n):
node=q.pop(0)
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res