BM28. 二叉树的最大深度
描述
求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。
（注：叶子节点是指没有子节点的节点。）
数据范围：
，树上每个节点的val满足 
要求： 时间复杂度)
要求： 时间复杂度
示例1
输入:
{1,2}
输出:
2
示例2
输入:
{1,2,3,4,#,#,5}
输出:
3
BM28. 二叉树的最大深度
描述
示例1
输入:
{1,2}
输出:
2
示例2
输入:
{1,2,3,4,#,#,5}
输出:
3
C++ 解法, 执行用时: 0ms, 内存消耗: 8816KB, 提交时间: 2015-04-03
/**
* 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)
return 0;
int mx = 1;
queue<pair<TreeNode *, int> > q;
q.push(make_pair(root, 1));
while (!q.empty()) {
pair<TreeNode *, int> p = q.front();
q.pop();
if (p.first -> left == NULL && p.first -> right == NULL)
continue;
mx = max(mx, p.second + 1);
if (p.first -> left != NULL)
q.push(make_pair(p.first -> left, p.second + 1));
if (p.first -> right != NULL)
q.push(make_pair(p.first -> right, p.second + 1));
}
return mx;
}
};
C++ 解法, 执行用时: 0ms, 内存消耗: 8816KB, 提交时间: 2015-04-03
/**
* 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) {
int left,right;
if(root==NULL)
return 0;
left=maxDepth(root->left);
right=maxDepth(root->right);
return left>right?left+1:right+1;
}
};
C++ 解法, 执行用时: 0ms, 内存消耗: 8816KB, 提交时间: 2015-04-03
/**
* 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;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return 1+max(left,right);
}
};
C++ 解法, 执行用时: 0ms, 内存消耗: 8816KB, 提交时间: 2015-04-02
/**
* 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;
else
{
if(root->left != NULL && root->left != NULL)
return 1 + (maxDepth(root->left) > maxDepth(root->right) ? maxDepth(root->left) : maxDepth(root->right));
else if(root->left != NULL)
return 1 + maxDepth(root->left);
else
return 1 + maxDepth(root->right);
}
}
};
C++ 解法, 执行用时: 0ms, 内存消耗: 8816KB, 提交时间: 2015-04-01
/**
* 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 1+max(maxDepth(root->left),maxDepth(root->right));
}
};