美文网首页
111. 二叉树的最小深度

111. 二叉树的最小深度

作者: 一角钱技术 | 来源:发表于2020-08-23 01:16 被阅读0次

    111. 二叉树的最小深度

    给定一个二叉树,找出其最小深度。
    最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

    示例:
    
    给定二叉树 [3,9,20,null,null,15,7],
        3
       / \
      9  20
        /  \
       15   7
    

    返回它的最小深度 2.

    算法思路

    这里先注意一下 1, 2 这个测试用例,写在前面。
    题目中的说明:叶子节点是指没有子节点的节点,针对 1,2 这个测试案例,1 不是叶子节点,2 才是叶子节点。

    解决这道题的关键是弄清楚递归终止条件:

    • 叶子节点的定义是左孩子或者右孩子都为 null 时叫做叶子节点
    • 当 root 节点左右孩子都为 null 时,返回 1
    • 当 root 节点左右孩子有一个为空时,返回不为空的孩子节点的深度
    • 当 root 节点左右孩子都不为空时, 返回左右孩子较小深度的节点值

    方法1: DFS

    class Solution {
        // DFS 递归 + 分治 时间O(n) 空间O(n)
        public int minDepth1(TreeNode root) {
            if (root == null) {
                return 0;
            }
            if (root.left == null && root.right != null) {
                return 1 + minDepth(root.right);
            }
            if (root.left != null && root.right == null) {
                return 1+ minDepth(root.left);
            }
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        }
    }
    

    方法2: BFS

    class Solution {
        // BFS 时间O(n) 空间O(n)
        public int minDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.add(root);
            int level = 1;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode curr = queue.poll();
                    if (curr.left == null && curr.right == null) {
                        return level;
                    }
                    if (curr.left != null) queue.add(curr.left);
                    if (curr.right != null) queue.add(curr.right);
                }
                level++;
            }
            return -1;
        }
    }
    

    以上谢谢大家,求赞求赞求赞!

    💗 大佬们随手关注下我的wx公众号【一角钱小助手】和 掘金专栏【一角钱】 更多题解干货等你来~~

    相关文章

      网友评论

          本文标题:111. 二叉树的最小深度

          本文链接:https://www.haomeiwen.com/subject/trxujktx.html