二叉树的遍历
时间: 2023-06-21 21:14:00 浏览: 36
二叉树的遍历有三种基本方式:
1. 前序遍历(Preorder Traversal):先访问根节点,然后按照先左后右的顺序递归访问左子树和右子树。
2. 中序遍历(Inorder Traversal):按照先左后根再右的顺序递归访问左子树、根节点、右子树。
3. 后序遍历(Postorder Traversal):按照先左后右再根的顺序递归访问左子树、右子树,最后访问根节点。
递归算法实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = [root.val]
res += self.preorderTraversal(root.left)
res += self.preorderTraversal(root.right)
return res
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
res += self.inorderTraversal(root.left)
res.append(root.val)
res += self.inorderTraversal(root.right)
return res
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
res += self.postorderTraversal(root.left)
res += self.postorderTraversal(root.right)
res.append(root.val)
return res
```
迭代算法实现:
```python
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res, stack = [], [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res, stack, cur = [], [], root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
node = stack.pop()
res.append(node.val)
cur = node.right
return res
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res, stack, pre = [], [], None
while root or stack:
if root:
stack.append(root)
root = root.left
else:
node = stack[-1]
if node.right and node.right != pre:
root = node.right
else:
res.append(node.val)
pre = node
stack.pop()
return res
```