題目：

Given a binary tree, find its minimum depth.

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

代碼：

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int minDepth(TreeNode* root) {if (!root) return 0;if ( !root->left && !root->right) return 1;if ( root->left && root->right ) return std::min( Solution::minDepth(root->left)+1, Solution::minDepth(root->right)+1);if ( root->left ) return Solution::minDepth(root->left)+1;if (root->right ) return Solution::minDepth(root->right)+1;} };

tips：

深搜思路（遞歸實現）。這里需要控制向下進行的條件。

1. 如果root是NULL，返回0

2. 如果root不是NULL，且left和right都是NULL，則到達葉子節點返回1（代表算上葉子節點的那一層）

3. 如果root->left和root->right都不為NULL，則繼續往兩邊深搜

4. 如果root不是NULL，但root->left或root->right哪一方為NULL，則為NULL的一端不會再有葉子節點出現，不能再往下走了。

完畢。

============================================

第二次過這道題，上來沒有把終止條件想完全。終止條件應該是達到葉子簡單root->left root->right都為空。

修改了一次后AC了。

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int minDepth(TreeNode* root){if ( !root ) return 0;int min_depth = INT_MAX;Solution::depth(root, min_depth, 1);return min_depth;}static void depth(TreeNode* root, int& min_depth, int dep){if ( !root->left && !root->right ) min_depth = min(min_depth,dep); if ( root->left ) Solution::depth(root->left, min_depth, dep+1);if ( root->right ) Solution::depth(root->right, min_depth, dep+1);} };

?

轉載于:https://www.cnblogs.com/xbf9xbf/p/4508762.html

總結

以上是生活随笔為你收集整理的【Minimum Depth of Binary Tree】cpp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。