算法之二叉树的深度 - 翁先森的博客

剑指 Offer 55 - I. 二叉树的深度（leecode 104）#

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

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

1.递归实现

思路：在存在节点的情况下，每次设置一个起始深度1，之后去遍历他的左子树和右子树找出最大层级，就像这样一个个节点去找

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

2.栈迭代实现

思路：

通过前序遍历或者其他什么遍历，每次向栈中存储一个对象保存节点以及上面遍历过的节点深度，之后拿max值和节点深度值做Math.max比较，找出最大的深度就行，重点是每一次都需要存深度

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val) {
4
 *     this.val = val;
5
 *     this.left = this.right = null;
6
 * }
7
 */
8
/**
9
 * @param {TreeNode} root
10
 * @return {number}
11
 */
12
var maxDepth = function(root) {
13
    if (!root) return 0
14

15
    let max = 0
16
    const stack = [[root, 0]]
17

18
    while (stack.length) {
19
        const [node, p] = stack.pop()
20

21
        max = Math.max(max, p + 1)
22

23
        node.left && stack.push([node.left, p + 1])
24
        node.right && stack.push([node.right, p + 1])
25
    }
26

27
    return max
28
};