[LeetCode 104] Maximum Depth of Binary Tree

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.

Diffculty
Medium

Similar Problems
[LeetCode 110] Balanced Binary Tree Easy [LeetCode 111] Minimum Depth of Binary Tree Easy

Analysis

首先要理解二叉树深度的概念，如下：

• 如果二叉树只有一个节点，那么深度就是 1 。
• 如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加 1。同样，如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加 1 。
• 如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加 1 。

与这题相关的题目比如求一颗二叉树是否是平衡二叉树，那么就可以通过判断左右子树高度/深度是否一样来判断。

Solutions

1. 递归

class Solution {
public:
    int maxDepth(TreeNode *root) {
        if(root == nullptr) return 0;
        int maxleft = maxDepth(root->left);
        int maxright = maxDepth(root->right);
        if(maxleft == 0)
            return maxright + 1;
        else if(maxright == 0)
            return maxleft + 1;
        else 
            return max(maxleft, maxright) + 1;
    }
};

1. 非递归，层次遍历

class Solution {
public:
    int maxDepth(TreeNode *root) {
        // 层序遍历计算树的层数即可，nullptr 作为每一层节点的分割标志
        if(root == nullptr) return 0;
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);
        while(q.empty() == false){
            TreeNode *p = q.front();
            q.pop();
            if(p != nullptr){
                if(p->left)q.push(p->left);
                if(p->right)q.push(p->right);
            }
            else{
                res++;
                if(q.empty() == false)q.push(nullptr);
            }
        }
        return res;
    }
};