二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度。

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

说明: 叶子节点是指没有子节点的节点。

示例

给定二叉树 [3,9,20,null,null,15,7]，

image.png

返回最大深度3

题目分析

• 给定一个二叉树，无论是求其最大深度，还是最小深度，都可以用广度优先遍历来解，同一套模板，只是遍历终止条件不同。
• 递归求解
  BFS求解（C++）

int maxDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        queue<TreeNode*> Q;

        Q.push(root);
        int depth = 0;
        while(!Q.empty()){
            int sz = Q.size();
            for (int i=0; i<sz; i++){
                TreeNode* root = Q.front();
                Q.pop();
                if (root->left)
                    Q.push(root->left);
                if (root->right)
                    Q.push(root->right);
            }
            depth += 1;
        }
        return depth;
    }

时间复杂度O(n)，空间复杂度O(n)

递归求解(python)

def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

时间复杂度O(n)，空间复杂度O(height) height是二叉树的高度。