【力扣】二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

层序遍历求深度

流程

层序遍历是对二叉树每一层进行遍历，我们定义一个深度，在遍历完一层后，深度+1。

代码实现

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr)
            return 0;
        queue<TreeNode*> que;
        que.push(root);
        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left)
                    que.push(node->left);
                if (node->right)
                    que.push(node->right);
            }
            depth++;
        }
        return depth;
    }
};

递归求深度

流程

根节点的高度就是二叉树的最大深度，通过后序求的根节点高度来求的二叉树最大深度。

代码实现

class Solution {
public:
    int maxDepth(TreeNode* root) {
        return getHeight(root);
    }
    int getHeight(TreeNode* node){
        if(node==nullptr) return 0;
        int leftHeight=getHeight(node->left);
        int rightHeight=getHeight(node->right);
        return 1+max(leftHeight,rightHeight);
    }
};