二叉树的遍历
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]
