104、二叉树的最大深度
[二叉树的最大深度][https://leetcode.cn/problems/maximum-depth-of-binary-tree/]
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
时间复杂度 O(n)
空间复杂度 O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr){
return 0;
}
return max(maxDepth(root->right), maxDepth(root->left)) + 1;
}
};
|
100、相同的树
[相同的树][https://leetcode.cn/problems/same-tree/]
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == nullptr || q == nullptr){
if(p == nullptr && q == nullptr){
return true;
}else{
return false;
}
}
return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
|
101、对称二叉树
[对称二叉树][https://leetcode.cn/problems/symmetric-tree/]
给你一个二叉树的根节点 root ， 检查它是否轴对称。
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
|
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == nullptr || q == nullptr){
if(p == nullptr && q == nullptr){
return true;
}else{
return false;
}
}
return p->val == q->val && isSameTree(p->right, q->left) && isSameTree(p->left, q->right);
}
bool isSymmetric(TreeNode* root) {
return isSameTree(root->right, root->left);
}
};
|
110、平衡二叉树
[平衡二叉树][https://leetcode.cn/problems/balanced-binary-tree/description/]
给定一个二叉树，判断它是否是高度平衡的二叉树。
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
|
class Solution {
public:
int dfs(TreeNode* root){
if(root == nullptr){
return 0;
}
int left = dfs(root->left);
if(left == -1){
return -1;
}
int right = dfs(root->right);
if(right == -1){
return -1;
}
if(abs(left - right) > 1){
return -1;
}
return max(left, right) + 1;
}
bool isBalanced(TreeNode* root) {
return dfs(root) == -1? false : true;
}
};
|
199、二叉树的右视图
[二叉树的右视图][https://leetcode.cn/problems/binary-tree-right-side-view/]
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
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
|
class Solution {
public:
vector<int> ans;
void dfs(TreeNode* root, int deep){
if(root == nullptr){
return;
}
if(deep == ans.size()){
ans.push_back(root->val);
}
dfs(root->right, deep + 1);
dfs(root->left, deep + 1);
}
vector<int> rightSideView(TreeNode* root) {
dfs(root, 0);
return ans;
}
};
|
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
分类讨论
当前节点为空 返回当前
当前为q 返回当前
当前为p 返回当前
左右子树都有 返回当前
只有右有 返回右边的节点
只有左有 返回左边的节点
都没有 返回空
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
|
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == p || root == q || root == NULL){
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left != NULL && right != NULL){
return root;
}else if(left == NULL){
return right;
}else{
return left;
}
}
};
|
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
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
|
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
int x = root->val;
int p_v = p->val;
int q_v = q->val;
if(q_v < x && p_v < x){
return lowestCommonAncestor(root->left, p, q);
}
if(q_v > x && p_v > x){
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
};
|
