題目

給定一個 Binary Tree，求最大深度。

Tree

1. 定義

• 由 1 個以上的節點所構成的集合，不可為空。
• 至少有一個特殊節點，稱為 Root。
• 其餘 Nodes 分成

2. 術語

Root

• 沒有父節點的節點
• 一棵樹只能有唯一的root

Degree

• 一個節點的子節點數目
• 如圖綠色標示，degree為2

Parent(父節點) & Child(子節點) & Sibling(兄弟節點)

• 如紅色部分標示，30往下連接20和40，30為20與40的父節點，20和40為30的子節點
• 20和40的父節點相同，所以20與40互為Sibling

Non-leaf(非葉子節點) & Leaf(葉子節點)

• 有子節點的稱作 Non-leaf node
• 沒有子節點的稱作　leaf node

Level(層次)

• 自root到該node的距離
• root的level = 1

Depth

• 即最大level
  

Binary Tree

1. 定義

• 0個以上節點的集合 (注意: 可以為空的，跟Tree不一樣哦!)
• 每個節點最多只有兩個子節點的樹，節點左邊稱為左子樹 (left child)、節點右邊稱為右子樹 (right child)。
• 子樹有左、右方向的分別，如下圖 (注意: Tree沒有哦!)
  

2. 分類

完全二元樹 (Fully Binary Tree)

• 高度為k
• 具有2^k-1個node
• 除了leaf，都有left child和right child。

完整二元樹 (Complete Binary Tree)

• 與Fully Binary Tree就在最後一層的node沒有滿，且最後一層的node都靠左。
  

解法

了解什麼是Binary tree之後，要解這個就不難啦
把所有的節點走過一次，並記錄最大層數。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int* res = new int(0);
        cout<<*res;
        search(root,res,0);
        return *res;
    }
    void search(TreeNode* cur, int* res,int counter){
        if(cur==NULL){
            if(counter > *res){
                *res = counter;
            }
        }
        else{
            search(cur->left,res,counter+1);
            search(cur->right,res,counter+1);
        }
    }
};