FXTi's blog
0%

maximum-depth-of-binary-tree

Posted on Edited on

Maximum Depth of Binary Tree – LeetCode 104

Problem

Description

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:    
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        if(root->left == root->right) return 1;
        return 1 + max(maxDepth(root->left),maxDepth(root->right));
    }
};

思路

又是一道二叉树的题目，依旧可以用DFS的递归解，及其简洁。时间复杂度$O(n)$，$n$为节点数，空间复杂度$O(n)$。
耗时$6$ ms，排名$78.39\%$

Better

思路

同样可以使用基于Queue的BFS迭代法，这里按照每一层不断向下前进。时间复杂度$O(n)$，$n$为节点数，空间复杂度$O(n)$。
耗时$6$ ms，排名$78.39\%$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:    
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int level = 0;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            ++level;
            int size = q.size();
            for(int i = 0; i != size; ++i){
                TreeNode *node = q.front(); q.pop();
                if(node){
                    if(node->left) q.push(node->left);
                    if(node->right) q.push(node->right);
                }
            }
        }
        return level;
    }
};