[LeetCode Hot 100] LeetCode111. 二叉树的最小深度

题目描述

思路

二叉树的最小深度就是第一个叶子节点所在的层数

方法一：前序遍历(递归、dfs)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int res = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        dfs(root, 1);
        return res;
    }
    private void dfs(TreeNode node, int level) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            res = Math.min(res, level);
            // 这里return可以写也可以不写,写的话相当于剪枝效果。
            return;
        } 
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}

方法二：层序遍历(bfs)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root == null) return 0;
        queue.offer(root);
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                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 level;
                }
            }
            level += 1;
        }
		// 代码不会走到这里
        throw new RuntimeException("Error!!!");
    }
}