This is the 10th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the 10th day of my participation in August more text, today brings you about the binary tree related algorithm problem is the minimum depth of binary tree, the text is as follows:

Topic:

Given a binary tree, find its minimum depth.

Minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node.

Note: A leaf node is a node with no child nodes.

Example 1:

Input: root = [3,9,20,null,null,15,7] output: 2Copy the code

Example 2:

Input: root = [2, null, 3, null, 4, null, 5, null, 6] output: 5Copy the code

Their thinking

The first thing to think about is using a depth-first search method to traverse the whole tree and record the minimum depth.

For each non-leaf node, we only need to calculate the minimum leaf node depth of its left and right subtrees respectively. This turns a big problem into a small problem that can be solved recursively.

  • If root of the current node is empty, the height of the tree is 0, which is also the minimum value.

  • If the left and right subtrees of the current node root are null, the height of the tree is 1. 1 is also the minimum value.

  • In other cases, the current node has a value and the minimum depth of the left and right subtrees needs to be calculated respectively. The minimum depth +1 is returned. +1 indicates that the current node has a depth.

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) {return 0;
        } else if (root.left == null) {
            return minDepth(root.right) + 1;
        } else if (root.right == null) {return minDepth(root.left) + 1;
        } else {
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1; }}}Copy the code

The last

Complexity analysis

  • Time complexity: O(N), where N is the number of nodes in the tree. Each node is accessed once.

  • Space complexity: O(H), where H is the height of the tree. The spatial complexity is mainly determined by the overhead of stack space in recursion. In the worst case, the tree is chained and the spatial complexity is O(N). On average, the height of the tree is correlated logarithmically with the number of nodes, and the space complexity is order log N.