題目

給定一個二叉樹蒋搜，求最小深度(根節(jié)點(diǎn)到葉子結(jié)點(diǎn)最少的節(jié)點(diǎn)數(shù))矮湘。

原理

深度優(yōu)先

先找到所有的葉子節(jié)點(diǎn)，然后從葉子節(jié)點(diǎn)數(shù)到根節(jié)點(diǎn)荧琼，找到最少的節(jié)點(diǎn)數(shù)。

廣度優(yōu)先

從根節(jié)點(diǎn)遍歷所有葉子結(jié)點(diǎn)差牛，找到最少的節(jié)點(diǎn)數(shù)命锄。創(chuàng)建一個隊(duì)列，將根節(jié)點(diǎn)及其深度放入隊(duì)列偏化，取出后判斷其左右節(jié)點(diǎn)脐恩，如果為null返回深度，否則將左右節(jié)點(diǎn)放入隊(duì)列侦讨，深度為上一節(jié)點(diǎn)深度 +1驶冒，以此類推。

代碼

深度優(yōu)先

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, node7, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        System.out.println(minDepthByDeepFirst(node1));
    }

    private static int minDepthByDeepFirst(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int min = Integer.MAX_VALUE;
        if (root.left != null) {
            min = Math.min(min, minDepthByDeepFirst(root.left));
        }
        if (root.right != null) {
            min = Math.min(min, minDepthByDeepFirst(root.right));
        }
        return min + 1;
    }

廣度優(yōu)先

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, node7, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        System.out.println(minDepthByScopeFirst(node1));
    }

    private static int minDepthByScopeFirst(TreeNode root) {
        if (root == null) {
            return 0;
        }
        root.deep = 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left == null && node.right == null) {
                return node.deep;
            }
            if (node.left != null) {
                node.left.deep = node.deep + 1;
                queue.offer(node.left);
            }
            if (node.right != null) {
                node.right.deep = node.deep + 1;
                queue.offer(node.right);
            }
        }
        return 0;
    }