首页 > 代码库 > [Leetcode][Tree][Depth of Binary Tree]
[Leetcode][Tree][Depth of Binary Tree]
计算树的深度
1、minimum depth of binary tree
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 int minDepth(TreeNode *root) {13 if (root == NULL) {14 return 0;15 }16 if (root->left == NULL && root->right == NULL) {17 return 1;18 }19 int left = INT_MAX;20 int right = INT_MAX;21 if (root->left != NULL) {22 left = minDepth(root->left);23 }24 if (root->right != NULL) {25 right = minDepth(root->right);26 }27 return min(left, right) + 1;28 }29 };
总结：刚开始用非常简单的递归，发现wa了，是由于root结点在有一个子树的时候，不算是叶子，需要特殊处理。
又写了一个迭代的版本，也可以用作树的层次遍历。回忆了一下stack和queue的用法。
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 int minDepth(TreeNode *root) {13 int result = INT_MAX;14 queue<pair<TreeNode*, int>> q;15 if (root != NULL) {16 q.push(make_pair(root,1));17 } else {18 return 0;19 }20 while (!q.empty()) {21 auto node = q.front().first;22 auto depth = q.front().second;23 q.pop();24 if (node->left == NULL && node->right == NULL) {25 result = min(result, depth);26 }27 if (node->left != NULL) {28 q.push(make_pair(node->left, depth + 1));29 }30 if (node->right != NULL) {31 q.push(make_pair(node->right, depth + 1));32 }33 }34 return result;35 }36 };
2、Maximum depth of binary tree
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int maxDepth(TreeNode *root) { if (root == NULL) { return 0; } return max(maxDepth(root->left), maxDepth(root->right)) + 1; /* if (root->left == NULL && root->right == NULL) { return 1; } int left = INT_MIN; int right = INT_MIN; if (root->left != NULL) { left = maxDepth(root->left); } if (root->right != NULL) { right = maxDepth(root->right); } return max(left, right) + 1; */ }};
CE了一次。。又不小心把单词拼错了。。
总结：maximum depth用了非常简单的递归，但是这种方法用在Minimum上就不行，需要对root结点进行特殊的处理。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。