[LeetCode] 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,15,7],

3
   /   9  20
    /     15   7

return its depth = 3.

Analyse

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

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

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

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();
            for (int i = 0; i < layer_count; ++i)
            {
                TreeNode* tmp = que.front();
                que.pop();

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

            ++depth;
        }

        return depth;
    }

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

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