2019-02-10

111. Minimum Depth of Binary Tree

Minimum Depth of Binary Tree:题目链接

BFS

思路：借助队列首先根节点入队，此时depth=1，然后将depth=1的结点出队，出队的同时将depth=1的结点的左右孩子入队，此时depth = 2，将depth = 2的结点出队并将其左右孩子入队，同理第N层也是这样，在此过程中检查是否有结点是叶节点，有说明该叶节点对应的深度就是最小深度

class Solution {
    
    // BFS  时间复杂度O(N)  空间复杂度O(M) M:队列的长度
    public int minDepth(TreeNode root) {
        if (root == null) { // 树空
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  // 根节点入队
        int depth = 0;      // 二叉树最小深度 初始为0
        while (!queue.isEmpty()) { // 队列不空
            depth++;  // 深度+1 
            // 获取当前层次的所有结点 并将其左右孩子入队
            for (int size = queue.size(); size > 0; --size) { 
                TreeNode front = queue.poll(); // 取出队首元素
                if (front.left == null && front.right == null) { // 如果队首元素是叶节点说明 该结点所在层次即为最小深度
                    return depth;
                }
                if (front.left != null) {  // 左孩子不空 左孩子入队
                    queue.offer(front.left);
                }
                if (front.right != null) { // 右孩子不空右孩子入队
                    queue.offer(front.right);
                }
            }
        }
        return depth;
    }
}

解法2：BFS入队列的是一个新建的结构体里面包含当前结点已经当前结点所在深度

class Solution {
    
    private class Node{
        TreeNode node;
        int level;
    
        public Node(){
            this(null,0);
        }
        public Node(TreeNode node,int level ){
            this.node = node;
            this.level = level;
        }
    }
    
    public int levelOrder(TreeNode root) {
        int res = 999999;
        if (root == null) {
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(root,1));
        
        while (!queue.isEmpty()) {
            Node front = queue.poll();
            if (front.node.left==null && front.node.right==null && front.level < res) {
                return  front.level;
            }
            if (front.node.left != null) {
                queue.add(new Node(front.node.left, front.level + 1));
            }
            if (front.node.right != null) {
                queue.add(new Node(front.node.right, front.level + 1));
            }
        }
        return res;
    }
    
    public int minDepth(TreeNode root) {
        return levelOrder(root);
    }
}

DFS-递归

class Solution {
    
    // 递归宏观语义：返回以root为根二叉树的最小深度
    public int minDepth(TreeNode root) {
        if (root == null) { // 树空
            return 0;
        }
        if (root.left == null && root.right == null) { // 当前结点左右孩子都空 返回root的深度1
            return 1;    
        }
        if (root.left == null) { // 左孩子空 右孩子不空 返回root深度 + root右子树最小深度
            return 1 + minDepth(root.right);
        }
        if (root.right == null) { // 右孩子空 左孩子不空 返回root深度 + root左子树最小深度
            return 1 + minDepth(root.left);  
        }
        int leftMinDepth = minDepth(root.left); // 递归左子树最小深度
        int rightMinDepth = minDepth(root.right); // 递归右子树最小深度
        return leftMinDepth < rightMinDepth ? leftMinDepth + 1 : rightMinDepth + 1; // 左右子树最小深度 + 根节点深度 
    }
}

本文标题:111. Minimum Depth of Binary Tree

文章作者:XerDemo

发布时间:2019-02-10, 22:00:25

最后更新:2019-02-12, 09:16:41

原始链接:https://xerdemo.github.io/2019/02/10/111-Minimum-Depth-of-Binary-Tree/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。