C语言实现:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int maxDepth(struct TreeNode* root)
{
if(NULL == root)
{
return 0;
}
int llen = maxDepth(root->left) + 1;
int rlen = maxDepth(root->right) + 1;
return (llen > rlen)? llen :rlen;
}
C++实现
计算二叉树的最大深度,和102题一个套路,只不过不用存储每一层的结点:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
int level = 0;
queue<TreeNode *> queue;
if(root) queue.push(root);
while(!queue.empty())
{
level += 1;
int n = queue.size();
for(int i = 0;i < n;i++)
{
TreeNode * elem = queue.front();
if(elem->left) queue.push(elem->left);
if(elem->right) queue.push(elem->right);
queue.pop();
}
}
return level;
}
};
运行结果:
Runtime: 8 ms, faster than 92.88% of C++ online submissions for Maximum Depth of Binary Tree.
Memory Usage: 19.2 MB, less than 16.22% of C++ online submissions for Maximum Depth of Binary Tree.
递归写法:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL)
return 0;
return 1 + max(maxDepth(root->left),maxDepth(root->right));
}
};
运行结果:
Runtime: 8 ms, faster than 92.88% of C++ online submissions for Maximum Depth of Binary Tree.
Memory Usage: 19.6 MB, less than 16.22% of C++ online submissions for Maximum Depth of Binary Tree.
如果程序写成这样就会出错:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL)
return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return 1 + (left > right) ? left:right;
}
};
原因是+的优先级高,所以上面实际执行顺序是(1 + (left > right)) ? left:right;
所以在使用三目运算符时应该要特别注意这一点,当然最稳妥的方法就是对三目运算符加括号。
class Solution {
public:
int maxDepth(TreeNode* root) {
std::queue<TreeNode*> q;
int max_depth = 0;
if(!root) return max_depth;
q.push(root);
while(!q.empty())
{
int elem_cnt = q.size();
for(int i = 0;i < elem_cnt;i++)
{
TreeNode* curr = q.front();
q.pop();
if(curr->left) q.push(curr->left);
if(curr->right) q.push(curr->right);
}
max_depth += 1;
}
return max_depth;
}
};