Leetcode 104 - Maximum Depth of Binary Tree

題目

Problem#

給一個二元樹，要你回傳樹高

想法#

DFS 遍歷整顆樹，可用 backtracking 到 leaf 時紀錄走了多深，找最大即可
遍歷時可拆成，max( dfs(左子樹), dfs(右子樹) )

• 時間複雜度: $\mathcal{O}(N)$, N = number of nodes
• 空間複雜度: $\mathcal{O}(1)$

AC Code#

賞析#

• BFS
  • https://leetcode.com/problems/maximum-depth-of-binary-tree/discuss/34238/Clean-Java-Iterative-Solution

int bfs(TreeNode *t)
{
    stack<TreeNode*> s;
    s.push(t);
    int cnt = 0;

    while(!s.empty())
    {
        // 當前這層的 size
        int siz = s.size();
        while(siz > 0)
        {
            TreeNode *now = s.top(); s.pop();
            if(now->left)
                s.push(now->left);
            if(now->right)
                s.push(now->right);
            siz--;
        }
        cnt++;
    }

    return cnt;
}

• 精簡版
  • https://leetcode.com/problems/maximum-depth-of-binary-tree/discuss/1770060/C%2B%2B-oror-Recursive-oror-DFS-oror-Example-Dry-Run-oror-Well-Explained

int maxDepth(TreeNode* root) {
    if(!root) return 0;
    int l = maxDepth(root->left);
    int r = maxDepth(root->right);
    return max(l, r)+1;
}