{"id":4442,"date":"2018-12-15T08:34:32","date_gmt":"2018-12-15T16:34:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4442"},"modified":"2018-12-15T08:41:07","modified_gmt":"2018-12-15T16:41:07","slug":"leetcode-111-minimum-depth-of-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-111-minimum-depth-of-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 111. Minimum Depth of Binary Tree"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given a binary tree, find its minimum depth.<\/p>\n

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.<\/p>\n

Note:<\/strong>\u00a0A leaf is a node with no children.<\/p>\n

Example:<\/strong><\/p>\n

Given binary tree\u00a0[3,9,20,null,null,15,7]<\/code>,<\/p>\n

    3\r\n   \/ \\\r\n  9  20\r\n    \/  \\\r\n   15   7<\/pre>\n
return its minimum\u00a0depth = 2.<\/p>\n
Solution: Recursion<\/strong><\/h1>\n
Time complexity: O(n)<\/p>\n
Space complexity: O(n)<\/p>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua, 4 ms\r\nclass Solution {\r\npublic:\r\n  int minDepth(TreeNode* root) {\r\n    if (!root) return 0;\r\n    if (!root->left && !root->right) return 1;\r\n    int l = root->left ? minDepth(root->left) : INT_MAX;\r\n    int r = root->right ? minDepth(root->right) : INT_MAX;\r\n    return min(l, r) + 1;\r\n  }\r\n};<\/pre>\n\n<\/div>
Python3<\/h2>\n
\n\n
class Solution:\r\n  def minDepth(self, root):\r\n    if not root: return 0\r\n    if not root.left and not root.right: return 1\r\n    l = self.minDepth(root.left)\r\n    r = self.minDepth(root.right)\r\n    if not root.left: return 1 + r\r\n    if not root.right: return 1 + l\r\n    return 1 + min(l, r)<\/pre>\n<\/div><\/div>\n
Related Problem<\/strong><\/h1>\n