最小深度问题

二叉树的最小深度

题目描述

力扣链接🔗

注意此时的最小深度是根节点到最近的叶子节点。例如：

代码分析

递归遍历

遍历顺序上依然是后序遍历（因为要比较递归返回之后的结果）。

1. 确定递归函数的参数和返回值
   参数为要传入的二叉树根节点，返回的是int类型的深度。
2. 确定终止条件终止条件
   也是遇到空节点返回0，表示当前节点的高度为0。
3. 确定单层递归的逻辑这块和求最大深度可就不一样了
   最大深度是返回左右节点最大深度 + 1，而此时需要注意是叶子节点，所以需要进行判断，如果左节点为空，那么深度为 右节点深度 + 1 ， 反之为 左节点 + 1，都不为空，则为左右节点中最小的深度。

public int minDepth(TreeNode root) {
    return getDepth(root);
}
public int getDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = getDepth(root.left);
    int rightDepth = getDepth(root.right);
    if (root.left == null && root.right != null) {
        return 1 + rightDepth;
    } else if (root.right == null && root.left != null) {
        return 1 + leftDepth;
    } else {
        return 1 + Math.min(leftDepth, rightDepth);
    }
}

迭代法

使用层序遍历，还是注意判断左右孩子节点都为空时才返回最小深度。

/**
 * 层序遍历
 *
 * @param root
 * @return
 */
public int minDepth(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    int deep = 0; // 深度
    if (root == null) {
        return 0;
    }
    queue.offer(root);
    while (!queue.isEmpty()) {
        int len = queue.size();
        deep++; // 深度加一,需要放在前面，如果放在下一个while后后面,root null null 会少一层
        while (len > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            if (node.left == null && node.right == null) {
                return deep;
            }
            len--;
        }
    }
    return deep;
}