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.

 

思路：可以用recursive的方法，每次返回左右两个树的最小高度的最小值加1. 但是如果这个树不是完整二叉树，则需要在没有左树或者没有右树的情况下让没有的那一叉返回正无穷而不是0. 所以需要判断当root == NULL的时候，这个root是不是到最下面一层了。

 

代码：

 

class Solution { public: int helper(TreeNode *root, bool hasBrother){ if (root == NULL) return hasBrother? INT_MAX:0; int minl = helper(root->left, root->right!=NULL); int minr = helper(root->right, root->left!=NULL); return 1+min(minl, minr); } int minDepth(TreeNode *root) { return helper(root, false); } };

　　

 

 

转载于:https://www.cnblogs.com/tanghulu321/archive/2013/05/02/3053948.html

相关资源：数据结构—成绩单生成器