二叉樹的遍歷
1. 前序遍歷
1.1 遞歸前序遍歷
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
1.2 非遞歸前序遍歷
def preorderTraversal(self, root: TreeNode) -> List[int]:
dummy = TreeNode(0)
dummy.right = root
res, stack = [], [dummy]
while stack:
node = stack.pop().right
while node:
res.append(node.val)
stack.append(node)
node = node.left
return res
2 中序遍歷
2.1遞歸遍歷
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
2.2非遞歸中序遍歷
def inorderTraversal(self, root: TreeNode) -> List[int]:
dummy = TreeNode(0)
dummy.right = root
res, stack = [], [dummy]
while stack:
node = stack.pop()
res.append(node.val)
node = node.right
while node:
stack.append(node)
node = node.left
return res[1:]
3 后序遍歷
3.1 遞歸后序遍歷
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) +[root.val]
3.2 非遞歸后序遍歷
def postorderTraversal(self, root: TreeNode) -> List[int]:
dummy = TreeNode(0)
dummy.right = root
res, stack, pre = [], [dummy], None
while stack:
node = stack[-1]
if node.right and pre != node.right:
node = node.right
while node:
stack.append(node)
node = node.left
else:
res.append(stack.pop().val)
pre = node
return res[:-1]
