通知短信+运营短信,5秒速达,支持群发助手一键发送🚀高效触达和通知客户 广告
**一. 题目描述** 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. **二. 题目分析** 这道题属于二叉树的深度优先搜索,然后返回深度最小的值,可以递归(当然,也可以使用迭代)来实现。递归退出的条件是到达叶子节点或者到达空子树,使用空子树作为退出条件比较容易进行判断,只要该结点的指针值为`NULL`时,就可以判断空子树的深度为0。因此,可以将每个结点的左右两个子树的深度返回给父节点,父节点选择比较小的深度,然后再返回给祖先结点,以此类推,最后返回给根结点,得到最终结果。 这种方法的时间复杂度为:`O(n)`,空间复杂度为:`O(logn)`。 **三. 示例代码** ~~~ struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: int minDepth(TreeNode* root) { if (!root) return 0; int Result = 1; int Left = minDepth(root->left); int Right = minDepth(root->right); if (Left * Right) Result += Left > Right? Right : Left; else result += Right + Left; return Result; } }; ~~~ **四. 小结** 这是一道对二叉树进行递归来得到结果的题,递归在二叉树的相关题目中还是考察得比较多的。