Lintcode：二叉树的最小深度

问题：

给定一个二叉树，找出其最小深度。

二叉树的最小深度为根节点到最近叶子节点的最短路径上的节点数量。

样例：

样例 1:

输入: {} 输出: 0

样例 2:

输入: {1,#,2,3} 输出: 3 解释: 1 \ 2 / 3 它将被序列化为 {1,#,2,3}

样例 3:

输入: {1,2,3,#,#,4,5} 输出: 2 解释: 1 / \ 2 3 / \ 4 5 它将被序列化为 {1,2,3,#,#,4,5}

python：

""" Definition of TreeNode: class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, None """ class Solution: """ @param root: The root of binary tree @return: An integer """ def minDepth(self, root): # write your code here if root == None: return 0 else: lnum = self.minDepth(root.left) rnum = self.minDepth(root.right) if root.left == None or root.right == None: if root.left == root.right: return 1 elif root.left != None: return lnum+1 else: return rnum+1 else: return min(lnum, rnum)+1

C++:

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree * @return: An integer */ int minDepth(TreeNode * root) { // write your code here if(root == NULL) { return 0; }else{ int lnum = minDepth(root->left); int rnum = minDepth(root->right); if(root->left == NULL || root->right == NULL) { if(root->left == root->right) { return 1; }else if(root->left != NULL) { return lnum+1; }else{ return rnum+1; } }else{ return min(lnum,rnum)+1; } } } };