> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/iii.-binary-tree.md).

# III. Binary Tree

{% hint style="info" %}

* 增减节点
* 分而治之的思想  (Divide and conquer)
* 遍历（Traversal）
  {% endhint %}

### 遍历1

**Preorder Traversal  (前序遍历) :** root -> left preorder -> right preorder

Inorder Traversal  (中序遍历): left inorder -> root -> right inorder

Postorder Traversal  (后序遍历): left postorder -> right postorder -> root

![](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-MLzIPDMmBlR5fftkuZa%2F-MLzQBiR_B3CFJuuSsu6%2F1605234348682.jpg?alt=media\&token=002c668d-bc62-4eda-8565-e4906477d138)

### 遍历2

#### DFS（深度遍历）: stack

#### BFS（广度遍历）: queue (1. add None; 2. length of each level; 3. two queues)

{% tabs %}
{% tab title="add None" %}

```java
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = [root]
        
        while len(q) != 0:
            node = q.pop(0)
            q.append(None)
            left_value = node.val
            while node != None:
                if node.left != None:
                    q.append(node.left)
                if node.right != None:
                    q.append(node.right)
                node = q.pop(0)
        
        return left_value
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}