Wednesday, December 26, 2012

[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:    }
``````