The minimum depth of a binary tree

Given a binary tree, find its minimum depth.

The 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 that has no children.

See the LeetCode website for an example.

Source: LeetCode Link: https://leetcode-cn.com/probl… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution 1: Recursion

First, if root is null, it returns 0 directly.

Otherwise, call the recursive method minDepth(TreeNode root, int curDepth), root is the current node, and curDepth is the current depth. The recursive procedure is as follows:

  • If root is null, return directly;
  • Otherwise, increase curDepth by 1;
  • If one side of root’s left subtree or right subtree is NULL, call the recursive method with non-NULL subtree and curDepth, and return;
  • If neither the left subtree nor the right subtree of root is NULL, then both the left and right subtrees call recursive methods.

In the process, it needs to determine which is smaller, the current depth or result, result takes the smaller one, and finally returns result, which is the minimum depth of the number.

public class LeetCode_111 { public static int result = Integer.MAX_VALUE; public static int minDepth(TreeNode root) { if (root == null) { return 0; } minDepth(root, 0); return result; } public static void minDepth(TreeNode root, int curDepth) { if (root == null) { return; } curDepth++; if (root.left == null && root.right == null) { if (curDepth < result) { result = curDepth; } return; } if (root.left == null && root.right ! = null) { minDepth(root.right, curDepth); return; } if (root.left ! = null && root.right == null) { minDepth(root.left, curDepth); return; } minDepth(root.left, curDepth); minDepth(root.right, curDepth); } public static void main(String[] args) { TreeNode root = new TreeNode(2); root.right = new TreeNode(3); root.right.right = new TreeNode(4); root.right.right.right = new TreeNode(5); root.right.right.right.right = new TreeNode(6); System.out.println(minDepth(root)); }}

【 Daily Message 】
One morning I threw away all yesterday, and since then I have been light on my feet.