111. Minimum Depth of 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 down to the nearest leaf node.
寻找二叉树的最小深度:递归解法,返回深度最小子树的深度。
代码如下:
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 { 15 return 0; 16 } 17 if(root->left == NULL && root->right == NULL) 18 { 19 return 1; 20 } 21 else if(root->left == NULL) 22 { 23 return 1 + minDepth(root->right); 24 } 25 else if(root->right == NULL) 26 { 27 return 1 + minDepth(root->left); 28 } 29 else 30 { 31 int l = 1 + minDepth(root->left); 32 int r = 1 + minDepth(root->right); 33 return l > r ? r : l; 34 } 35 } 36 };