[LeetCode] 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.

» Solve this problem

[解题报告]

Recursion is the best friend of tree-related problems. Same here. If we define Min[K] as the minimal depth of node K(no matter where this K is in the tree). We can derive the transition function as

            Min[ K ] = min ( Min[K->left] , Min[K->right]) + 1

And, implement it as below. 

[Code]

1:    int minDepth(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(root == NULL)  
5:        return 0;  
6:      int lmin = minDepth(root->left);  
7:      int rmin = minDepth(root->right);  
8:      if(lmin ==0 && rmin ==0)  
9:        return 1;  
10:      if(lmin ==0)  
11:      {  
12:        lmin = INT_MAX;  
13:      }  
14:      if(rmin ==0)  
15:      {  
16:        rmin = INT_MAX;  
17:      }  
18:      return min(lmin, rmin) +1;  
19:    }