Dovis's blog

# 104. 二叉树的最大深度

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

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

    3
   / \
  9  20
    /  \
   15   7
# 深度为3
1
2
3
4
5
6

# 思路

  • 标签：DFS
  • 找出终止条件：当前节点为空
  • 找出返回值：节点为空时说明高度为 0，所以返回 0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值
  • 某层的执行过程：在返回值部分基本已经描述清楚
  • 时间复杂度：O(n) 空间复杂度：O(n)递归栈空间

作者：guanpengchn 链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/hua-jie-suan-fa-104-er-cha-shu-de-zui-da-shen-du-b/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) {
        return 0
    } else {
        let left = maxDepth(root.left)
        let right = maxDepth(root.right)
        return Math.max(left,right)+1
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# bfs广度优先

/*
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root == null) {
        return 0;
    }

    let maxDeep = 0;
    let queue = [root];

    while (queue.length) {
        let n = queue.length;
        // 一层一层遍历
        for (let i = 0; i < n; i++) {
            const curNode = queue.shift();
            if (curNode.left) queue.push(curNode.left);
            if (curNode.right) queue.push(curNode.right);
        }
        maxDeep++;
    }
    
    return maxDeep;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
  • 时间复杂度: O(N), N为节点数
  • 空间复杂度: 取决于队列存储的元素数量，最坏会达到 O(N)

← 590. N叉树的后序遍历 →