38. 二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
解题思路：
- 思路1: 使用递归思路，属于DFS（深度优先搜索），时间复杂度为
O(N)，空间复杂度：在最糟糕的情况下，树是完全不平衡的，例如每个结点只剩下左子结点，递归将会被调用N次（树的高度），因此保持调用栈的存储将是O(N)。但在最好的情况下（树是完全平衡的），树的高度将是log(N)。因此，在这种情况下的空间复杂度将是O(log(N))。 - 思路2: 使用迭代思路，引入一个栈，使用 DFS 策略访问每个结点，同时在每次访问时更新最大深度。时间复杂度为
O(N)，空间复杂度将是O(N)。
解答：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
// 解法1:
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(!pRoot)
return 0;
return max(TreeDepth(pRoot->left) + 1, TreeDepth(pRoot->right) + 1);
}
};
// 解法2:
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(!pRoot)
return 0;
queue<TreeNode *> que;
que.push(pRoot);
int depth = 0;
while(!que.empty())
{
// 队列中每次迭代都只存储了一层的元素
int size = que.size();
depth++;
for(int i = 0; i < size; ++i)
{
TreeNode *node = que.front();
que.pop();
if(node->left)
que.push(node->left);
if(node->right)
que.push(node->right);
}
}
return depth;
}
};
大家有兴趣可以访问我的个人博客，不定时更新一些内容哦！
图片来自必应壁纸
