leetcode-104 Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree

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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its depth = 3.

Analyse

计算二叉树的高度，很基础的问题

两种思路：递归和层序遍历

层序遍历的时候需要一个queue辅助，每次进while循环的时候queue里是树的一层的节点，出队列后将下一层的节点入队列，需要记录每一层有几个节点来区分不同层的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maxDepth(TreeNode* root) {
    if (!root) return 0;

    queue<TreeNode*> que;
    que.push(root);

    int depth = 0;
    while (!que.empty())
    {
        int layer_count = que.size();
        while (layer_count-- > 0)
        {
            TreeNode* tmp = que.front();
            que.pop();

            if (tmp->left) { que.push(tmp->left); }
            if (tmp->right) { que.push(tmp->right); }
        }

        ++depth;
    }

    return depth;
}

更好的办法是用递归做，但我没想到，贴一个leetcode上大佬的代码，递归两行解决问题，递归也太强了

1
2
3
4
5
int maxDepth(TreeNode* root)
{
    if(root==NULL){return 0;}
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}