111. Minimum Depth of Binary Tree

• Total Accepted: 114343
• Total Submissions:368035
• Difficulty: Easy

 

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.

 

思路：理解题意。

1. 左右子树如果有空，根的深度=非空的子树深度+1

2. 左右子树都不为空，根的深度=min(左子树深度，右子树深度)+1

 

代码：

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int minDepth(TreeNode* root) {13         if(root==NULL){14             return 0;15         }16         int left=minDepth(root->left),right=minDepth(root->right);17         return (!left||!right)?left+right+1:min(left,right)+1;18     }19 };