二叉树的最小深度(Minimum depth of binary tree)

二叉树的最小深度

题目:二叉树的最小深度

《程序员代码面试指南》第33题 P100 难度:原问题 士★☆☆☆ 进阶问题 将★★★★

本题书上有普通解法和进阶解法。进阶解法用到了遍历二叉树的神级方法——Morris遍历,暂时不看,有空回来补。

下面介绍普通解法。很简单,就是在遍历的过程中去发现所有的叶子结点,并且能够知道该叶子结点的高度。最后找到所有叶子结点高度中的最小值

牛客上没有这题,力扣上有深度优先搜索广度优先搜索两种方法。

DFS(时间复杂度O(N),空间复杂度O(H)):

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

不难发现,递归直到找到叶子结点后,返回深度1,然后从下往上逐层深度加1,并且每次左子树和右子树取最小深度。到第一层根节点处,同样,找出左子树和右子树的最小深度后,再返回深度加1,即加上根节点的深度,就是整个二叉树的最小深度

BFS(时间复杂度O(N),空间复杂度O(N)):

class Solution {
    class QueueNode {
        TreeNode node;
        int depth;

        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<QueueNode> queue = new LinkedList<QueueNode>();
        queue.offer(new QueueNode(root, 1));
        while (!queue.isEmpty()) {
            QueueNode nodeDepth = queue.poll();
            TreeNode node = nodeDepth.node;
            int depth = nodeDepth.depth;
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) {
                queue.offer(new QueueNode(node.left, depth + 1));
            }
            if (node.right != null) {
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }

        return 0;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

可以看出,使用了队列的数据结构,每次从队头取出一个节点的同时,将它的左子树和右子树(如果有的话)放入队尾,形成了层序遍历的过程。

对于广度优先搜索进行特别说明:

找到一个叶子节点时,直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小

这是因为广度优先搜索相当于层序遍历二叉树,如果一个节点是叶子结点,说明当前层和之前的所有层都没有出现过叶子结点(不然就已经返回了),所以第一个搜索到的叶子结点深度一定是最小的

————————

Minimum depth of binary tree

Title: minimum depth of binary tree

“Programmer code interview guide” question 33 P100 difficulty: original question ★☆☆☆ advanced question ★★★★

There are ordinary solutions and advanced solutions in this problem book. The advanced solution uses the divine method of traversing the binary tree – Morris traversal. Don’t look at it for the time being and come back to make up when you have time.

The general solution is introduced below. It is very simple to find all leaf nodes < / strong > during < strong > traversal, and know the height of the < strong > leaf node < / strong >. Finally, find the < strong > minimum value of all leaf node heights < / strong >.

Niuke doesn’t have this question. There are two methods on the force button: < strong > depth first search < / strong > and < strong > breadth first search < / strong >.

< strong > DFS < / strong > (time complexity O (n), space complexity O (H)):

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

It is not difficult to find that after recursion < strong > until the leaf node < / strong > is found, < strong > returns the depth of 1 < / strong >, then < strong > adds 1 < / strong > layer by layer from bottom to top, and < strong > each time the left and right subtrees take the minimum depth < / strong >. Go to the first layer < strong > root node < / strong >, similarly, find the minimum depth of the left and right subtrees, and then < strong > return the depth plus 1 < / strong >, that is, add the depth of the root node, which is < strong > the minimum depth of the whole binary tree < / strong >.

< strong > BFS < / strong > (time complexity O (n), space complexity O (n)):

class Solution {
    class QueueNode {
        TreeNode node;
        int depth;

        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<QueueNode> queue = new LinkedList<QueueNode>();
        queue.offer(new QueueNode(root, 1));
        while (!queue.isEmpty()) {
            QueueNode nodeDepth = queue.poll();
            TreeNode node = nodeDepth.node;
            int depth = nodeDepth.depth;
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) {
                queue.offer(new QueueNode(node.left, depth + 1));
            }
            if (node.right != null) {
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }

        return 0;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

It can be seen that the data structure of < strong > queue < / strong > is used. Each time < strong > takes out a node < / strong > from the head of the queue, its < strong > left subtree and right subtree < / strong > (if any) are placed in the tail of the queue < / strong >, forming the process of < strong > sequence history < / strong >.

Special instructions for < strong > breadth first search < / strong >:

When < strong > finds a leaf node < / strong >, < strong > directly returns the depth of the leaf node < / strong >. The breadth first search ensures that the depth of the first leaf node to be searched must be the smallest < / strong >.

This is because breadth first search is equivalent to < strong > sequence traversal < / strong > binary tree. If < strong > a node is a leaf node < / strong >, it means that < strong > there has been no leaf node < / strong > (otherwise it has been returned) in the current layer and all previous layers. Therefore, < strong > the depth of the first searched leaf node must be the smallest < / strong >.