111. 二叉树的最小深度

题目来源

111. 二叉树的最小深度

题目描述

在这里插入图片描述

题目解析

DP

算法：分治/动态规划/DFS
实现方式：自底向上/递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public  int minDepth(TreeNode root) {
        // 基本情况 dp[null] = 0 ，dp[叶子] = 1
        if (root == null){
            return 0;
        }
        if (root.right == null && root.left == null){
            return 1;
        }
        if (root.left == null){
            return minDepth(root.right) + 1;
        }
        if (root.right == null){
            return minDepth(root.left) + 1;
        }
        // 状态转移方程
        //              / dp[右孩子] + 1 ，左孩子为null
        // dp[非叶子] =    dp[左孩子] + 1 ，右孩子为null
        //              \ min(dp[左孩子], dp[右孩子]) + 1 ，左右孩子都不为null
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

在这里插入图片描述

回溯

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public  int minDepth(TreeNode root) {
        return helper(root, 1);
    }
    // depth：走过的路
    // root：当前状态[dp数组中的为]
    private int helper(TreeNode root, int depth){
        // 最小子状态
        if (root == null){
            return depth - 1;
        }
        if (root.right == null && root.left == null){
            return depth;
        }
        // 由状态变量得出选择列表
        // 该层调用返回，相当于回溯，因为上层的depth比该层小1
        if (root.left == null){
            return helper(root.right, depth + 1);
        }
        if (root.right == null){
            return helper(root.left, depth + 1);
        }
        return Math.min(helper(root.left, depth + 1), helper(root.right, depth + 1));
    }
}

–

层次遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
public int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++){
                TreeNode top = queue.poll();
                if (top.left == null && top.right == null){
                    return level;
                }
                if (top.left != null){
                    queue.offer(top.left);
                }
                if (top.right != null){
                    queue.offer(top.right);
                }
            }
            level++;
        }
        return level;
    }
}

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
public  int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 1));
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++){
                Pair<TreeNode, Integer> poll = queue.poll();
                TreeNode top = poll.getKey();
                int depth = poll.getValue();
                if (top.left == null && top.right == null){
                    return depth;
                }
                if (top.left != null){
                    queue.offer(new Pair<>(top.left, depth + 1));
                }
                if (top.right != null){
                    queue.offer(new Pair<>(top.right, depth + 1));
                }
            }
        }
        return 0;
    }
}

在这里插入图片描述

深度优先搜索

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
private int ans = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        helper(root, 0);
        return ans;
    }
    private void helper(TreeNode root, int depth){
        if (root == null){
            ans = depth;  // 易错点
            return;
        }
        depth = depth + 1;
        // 是叶子节点
        if (root.right == null && root.left == null){
            if (depth < ans){
                ans = depth;
            }
            return;
        }
        if (root.left != null){
            helper(root.left, depth);
        }
        if (root.right != null){
            helper(root.right, depth);
        }
    }
}

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        if (root.left == null){
            return minDepth(root.right) + 1;
        }
        if (root.right == null){
            return minDepth(root.left) + 1;
        }
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}