# 【LeetCode】Binary Tree 筆記

## Introduction 簡介
Binary Tree題目涉及大量的演算法，例如**traversal**、**recursive**、**backtracking等等**演算法

## Define 介紹
為每個節點**至多**只有**兩個分支**的樹，左分支稱作**左子樹**而右分支稱為**右子樹**

### Attribute 性質
:::warning
Leetcode定義與正常不太一樣，Leetcode為以節點數(node)當基準，而正常定義為以邊(edge)數量
:::

1. **Depth** : 節點的深度是指從**樹的根節點**到**該節點的節點數**，根節點的深度為1，**其他節點的深度是它們的父節點深度加1**。
1. **maximum depth(最大深度)**
從樹的根結點到**最遠**的葉子節點的節點量
2. **minimum depth(最小深度)**
從樹的根結點到**最近**的葉子節點的節點數量
2. **Height**
樹的高度是指從**根節點**到**最深的葉子節點的節點數量**。若樹是空的，其高度定義為0；若樹只有一個節點，其高度為1。
3. **每層的節點數量**
在二元樹中，第 $i$ 層最多有 $2^{(i-1)}$ 個節點
4. **節點數量**
二元樹的總節點數最多為 $2^h - 1$ ，其中 $h$ 為樹的高度。

## 樹的種類
1. **Full Binary Tree**
* 所有節點除了葉子節點外，都有兩個子節點
* 可以是不均衡的，也就是高度不一樣，這與Perfect Binary Tree相差別
2. **Perfect Binary Tree**
* 所有節點除了葉子節點外，都有兩個子節點
* 所有葉子節點都在同一層
3. **Complete Binary Tree**
* 除了最後一層，其他層全部填滿節點
* 最後一層節點都靠左連續
4. **Balanced binary Tree**
* 每一個節點的左右子樹高度差不大於一