Cabbage Java self study room covers core knowledge

104. Maximum depth of binary trees LeetCode Series (Java edition) 111. The minimum depth of a binary tree

Force buckles the original problem

111. Minimum depth of a binary tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Note: Leaf nodes are nodes that have 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

  • Implementation: DFS (depth-first search)
  • If the current node root is empty, the tree height is 0 and 0 is also the minimum value
  • If both the left and right subtrees of the current node root are empty, the height of the tree is 1, and 1 is also the minimum value
  • In other cases, the current node has a value and the minimum depth d degree of its left and right subtrees needs to be calculated respectively. The minimum depth +1 is returned. +1 indicates that the current node has one depth

Code implementation

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

Complexity analysis

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

  • Space complexity: O(N)O(N)O(N), where NNN is the number of nodes in the tree. The spatial complexity depends mainly on the overhead of the queue, and the number of elements in the queue does not exceed the number of nodes in the tree.

104. Maximum depth of binary trees LeetCode Series (Java edition) 111. The minimum depth of a binary tree