class Solution { public: int minDepth(TreeNode *root) { if (root == NULL) return 0; int min_depth = INT_MAX; dfs(root, 0, min_depth); return min_depth + 1; } void dfs(TreeNode *root, int cur_depth, int& min_depth) { if (root == NULL) return; if (cur_depth >= min_depth) return; // we come here means that cur_depth < min_depth if (root->left == NULL && root->right == NULL) { // this is a leaf node min_depth = cur_depth; return; } dfs(root->left, cur_depth + 1, min_depth); dfs(root->right, cur_depth + 1, min_depth); } };
采用dfs遍历,对于深度已经超过当前已有最小值得路径进行裁剪。不过这个深度的概念,自己的理解和题目中的好像有些偏差。当然也可以用bfs,因为是求最小高度平均时间上bfs能够更早的发现最小高度,但是空间上dfs来的更少。
LeetCode Minimum Depth of Binary Tree,布布扣,bubuko.com
LeetCode Minimum Depth of Binary Tree
原文:http://www.cnblogs.com/lailailai/p/3608018.html