福建省建设干部网站google服务框架

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

题解：找出最小深度也就是找出根节点相对所有叶子结点的最小高度，在这也表明了根节点的高度是变化的，相对不同的叶子结点有不同的高度。

代码如下：

class Solution {
public:int minDepth(TreeNode* root) {if(NULL == root) return 0;if(NULL == root->left && NULL!= root->right) return 1+minDepth(root->right);if(NULL != root->left && NULL== root->right) return 1+minDepth(root->left);return 1+min(minDepth(root->left),minDepth(root->right));  }
};

注意：

在树形数据结构中，叶子节点（leaf node）是没有子节点的节点。换句话说，叶子节点是树中没有任何子节点的终端节点。

在解题时要注意无左子树或无右子树的情况，若不考虑得到的最小深度必然是1，因为左子树或右子树为NULL时高度为0，那根节点高度必然是1。