# 二叉树的遍历

掌握两种方法进行二叉树的遍历，这里重点看迭代法是怎么写，迭代法使用栈来模拟递归中的栈，也可以使用一种通用方式进行前、中、后序遍历。

**递归法**

```python
def dfs(root) {
	// 前序遍历
	dfs(root.left)
	// 中序遍历
	dfs(root.right)
	// 后序遍历
}
```

**迭代法**：迭代法是用 stack 栈来模拟递归栈

下面这种写法可以**统一前序、中序、后序遍历方式的写法，只需要改变入栈顺序**

前序遍历：中，左，右  
中序遍历：左，中，右  
后序遍历：左，右，中

中序遍历：  
栈是一种  `先进后出`的结构，出栈顺序为`左，中，右`  
那么入栈顺序必须调整为倒序，也就是`右，中，左`

同理，如果是前序遍历，入栈顺序为  `右，左，中`；后序遍历，入栈顺序 `中，右，左`

> 有没有发现？迭代法入栈顺序与递归法的递归顺序正好相反！

```python
while stack:
    node = stack.pop()
    if node == None:
        continue
    if isinstance(node, int):
        ans.append(node)
    else:
		# 中序遍历
        stack.extend([node.right, node.val, node.left])
        # 前序遍历
        # stack.extend([node.right, node.left, node.val])
        # 后序遍历
        # stack.extend([node.val, node.right, node.left])
```

* 每个节点都只入栈一次，出栈一次
    

### 中序遍历

[94\. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/)

递归法：

```python
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []

        def dfs(root):
            if root == None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)
        dfs(root)
        return ans
```

**迭代法**：迭代法是用 stack 栈来模拟递归栈

```python
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node == None:
                continue
            if isinstance(node, int):
                ans.append(node)
            else:
                stack.extend([node.right, node.val, node.left])
        return ans
```

### 前序遍历

递归

```python
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(root):
            if root==None:
                return
            ans.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return ans
```

迭代

```python
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node == None:
                continue
            if isinstance(node, int):
                ans.append(node)
            else:
                stack.extend([node.right, node.left, node.val])
        return ans
```

### 后序遍历

[145\. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/)

递归

```python
class Solution:
    def postorderTraversal(self,root:Optional[TreeNode])->List[int]:
        ans= []
        def dfs(root):
            if root==None:
                return
            dfs(root.left)
            dfs(root.right)
            ans.append(root.val)
        dfs(root)
        return ans
```

迭代

```python
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node == None:
                continue
            if isinstance(node, int):
                ans.append(node)
            else:
                stack.extend([node.val, node.right, node.left])
        return ans
```

### 层次遍历

层次遍历需要借助队列进行层次遍历

```python
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root == None:
            return []
        ans = []
        q = deque([root])
        while q:
            floor = []
            for _ in range(len(q)):
                node = q.popleft()
                floor.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(floor)
        return ans
```