题目描述
输入一颗二叉树，求该树的深度。
解题思路
求二叉树深度，通常有两种做法。
- 一种是通过深度优先遍历得到二叉树的深度；
- 另一种是通过广度优先遍历（层次遍历）得到二叉树的深度；
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
struct TreeNode
{
int val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode (int x): val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
int TreeDepth(TreeNode* pRoot)
{
if (pRoot == NULL)
return 0;
int left = TreeDepth(pRoot->left);
int right = TreeDepth(pRoot->right);
return (left > right) ? (left + 1) : (right + 1);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| struct TreeNode
{
int val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode (int x): val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
int TreeDepth(TreeNode* pRoot)
{
if (pRoot == NULL)
return 0;
queue<TreeNode*> Q;
Q.push(pRoot);
int depth = 0;
while (!Q.empty())
{
int size = Q.size();
depth++;
for (int i = 0; i < size; i++)
{
TreeNode* temp = Q.front();
Q.pop();
if (temp->left)
Q.push(temp->left);
if (temp->right)
Q.push(temp->right);
}
}
return depth;
}
};
|
参考博文链接：https://cuijiahua.com/blog/2018/01/basis_38.html