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. Very simple, is to find all leaf nodes in the process of traversal, and be able to know the height of the leaf node. Finally, find the minimum height of all leaf nodes.

Niuke doesn't have this problem. There are two methods: depth first search and breadth first search.

DFS (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;
    }
}

Author: LeetCode-Solution
 Link: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

It is not difficult to find that after recursion until the leaf node is found, return the depth of 1, and then add 1 layer by layer from bottom to top, and take the minimum depth of the left subtree and the right subtree each time. To the root node of the first layer, similarly, find out the minimum depth of the left subtree and the right subtree, and then return the depth plus 1, that is, add the depth of the root node, which is the minimum depth of the whole binary tree.

BFS (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;
    }
}

Author: LeetCode-Solution
 Link: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

It can be seen that the data structure of the queue is used. Each time a node is taken out from the head of the queue, its left subtree and right subtree (if any) are put into the tail of the queue, forming a sequence traversal process.

Special instructions for breadth first search:

When a leaf node is found, the depth of the leaf node is returned directly. The nature of breadth first search ensures that the depth of the first leaf node to be searched must be the minimum.

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