This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

They’re saying, given a binary tree, you want to find the depth from the root node to the nearest leaf node.

For example, you are given a binary tree: 1 / \ 2, 4 / \ 816 This tree has three leaves, which are 2, 8, 16. The nearest leaf node is 2, and there are two nodes from the root node to 2, so the minimum depth is 2. For example, if you are given a binary tree: 1\2\4, the only leaf node in the tree is 4, and there are three nodes from the root to it, so the minimum depth is 3.Copy the code


Ii. Analysis of Ideas:

This problem is looking at tree traversal.

Because there is the most left (right) subtree case, so can not like the above question (maximum depth of binary tree) direct comparison. You need to compare the left and right subtrees.

Ideas:

  1. Recursive traversal (DFS)
  2. Simulate hierarchical traversal with queues (BFS)


Three,ACCode:

public class LeetCode_111 {

    // Time: o(n) Space: o(n) faster: 100%
    public int minDepth(TreeNode root) {

        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if(root.left ! =null&& root.right ! =null) {
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        }

        if(root.left ! =null) return minDepth(root.left) + 1;
        return minDepth(root.right) + 1;
    }

    // Time: o(n) Space: o(n), Faster: 80.09%
    public int minDepthWith(TreeNode root) {

        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;

        while(! queue.isEmpty()) {int size = queue.size();
            for (int i = 0; i < size; ++i) {

                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) return depth;
                if(node.left ! =null) queue.offer(node.left);
                if(node.right ! =null) queue.offer(node.right);
            }
            ++depth;
        }
        return -1; }}Copy the code


Iv. Summary:

Tree traversal template

There are four types of tree traversal:

  1. The former sequence traversal
  2. In the sequence traversal
  3. After the sequence traversal
  4. Level traversal

It can also be divided into depth-first traversal (DFS) and breadth-first traversal (BFS)

Hierarchy traversal: Is for breadth-first traversal.

Other traversal: Is for depth-first traversal.

1. Preorder traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    // Preorder traversal code
    
    traverse(root.left);
    traverse(root.right);
}
Copy the code

2. Middle order traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    
    // Preorder traversal code
    
    traverse(root.right);
}
Copy the code

3. Back-order traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    traverse(root.right);
    
    // Preorder traversal code
}
Copy the code

4. Hierarchy traversal

Queue simulation

void traverse(TreeNode root) {
    if (null == root) return;
    
    // Initialize the queue to add root to the queue
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    
    while(! q.isEmpty()) { TreeNode cur = q.poll();// Hierarchy traverses code
        System.out.println(root.val);
        
        if(cur.left ! =null) q.offer(cur.left);
        if(cur.right ! =null) q.offer(cur.right); }}Copy the code