07二叉树深度

最大深度

题目

104. 二叉树的最大深度

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

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

示例 1：


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

示例 2：


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

提示：

树中节点的数量在 [0, 104] 区间内。

100 <= Node.val <= 100

思路

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。 • 二叉树节点的深度：根节点到该节点的路径条数、或者节点数（取决于深度从0开始还是从1开始） • 二叉树节点的高度：指从该节点到叶子节点的边条数或者节点数（取决于高度从0开始还是从1开始）

前序遍历中，首先访问根节点，然后访问其左右子树，因此求得的是从根节点到当前节点的路径长度，也就是节点的深度。后序遍历则是先访问子树，再访问根节点，最终得到的是从当前节点到其叶子节点的路径长度，也就是节点的高度。简单来说，前序强调从根到节点的深度，后序强调节点到叶子节点的高度。

Ts实现

递归后序


function maxDepth(root: TreeNode | null): number {
    const getDepth = (node: TreeNode) => {
        if (!node) return 0;
        const leftDepth = getDepth(node.left); // 左
        const rightDepth = getDepth(node.right); // 右
        const depth = 1 + Math.max(leftDepth, rightDepth); // 中
        return depth;
    }
    return getDepth(root);
};

递归前序


function maxDepth(root: TreeNode | null): number {
    const getDepth = (node: TreeNode, depth: number) => {
        result = depth > result ? depth : result;
        if (!node.left && !node.right) return; // 叶子节点不用递归了
        if (node.left) {
            getDepth(node.left, depth + 1); // 子树肯定比根多一层
        }
        if (node.right) {
            getDepth(node.right, depth + 1);
        }
        return;
    }
    let result: number = 0;
    if (root === null) return result;
    getDepth(root, 1); // 根节点为第一层，
    return result;
};

迭代层序遍历

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。


function maxDepth(root: TreeNode | null): number {
    const queue: TreeNode[] = [];
    let depth: number = 0;
    if (!root) return 0;
    queue.push(root);
    while(queue.length) {
        const size = queue.length;
        for(let i = 0; i < size; i++) {
            const cur = queue.shift();
            if (cur.left) queue.push(cur.left);
            if (cur.right) queue.push(cur.right);
        }
        depth++;
    }
    return depth;
};

最小深度

题目

111. 二叉树的最小深度labuladong 题解思路

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例 1：


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

示例 2：


输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

树中节点数的范围在 [0, 105] 内

1000 <= Node.val <= 1000

思路

题还有一个误区，在处理节点的过程中，最大深度很容易理解，最小深度就不那么好理解，如图：

这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。

什么是叶子节点，左右孩子都为空的节点才是叶子节点

Ts实现

递归后序遍历


function minDepth(root: TreeNode | null): number {
    const getDepth = (node: TreeNode) => {
        if (!node) return 0;
        let leftDepth = getDepth(node.left); // 
        let rightDepth = getDepth(node.right);

        if (!node.left && node.right) {
            return 1 + rightDepth;
        }

        if (node.left && !node.right) {
            return 1 + leftDepth;
        }

        return  1 + Math.min(leftDepth, rightDepth);
    }

    return getDepth(root);
};

叶子节点返回1，然后回溯

递归前序遍历


function minDepth(root: TreeNode | null): number {
    if (!root) return 0;
    let result: number = Infinity;
    const getDepth = (node: TreeNode, depth: number) => {
        if (!node) return;
        if (!node.left && !node.right) { // 中，叶子节点
            result = Math.min(result, depth);
        }

        if(node.left) {
            getDepth(node.left, depth + 1);
        }

        if (node.right) {
            getDepth(node.right, depth + 1);
        }
        return;
    }
    getDepth(root, 1);
    return result;
};

迭代层序遍历

最简单


function minDepth(root: TreeNode | null): number {
    if (!root) return 0;
    const queue: TreeNode[] = [];
    let depth: number = 0;
    queue.push(root);
    while(queue.length) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const cur = queue.shift();
            if (!cur.left && !cur.right) {
                return depth + 1;
            }
            if (cur.left) queue.push(cur.left);
            if (cur.right) queue.push(cur.right);
        }
        depth++;
    }
    return depth;
};