本文最后更新于：2023年4月15日 晚上
二叉树
对于二叉树的问题, 一般都有递归/非递归两种写法
1 | 剑指 Offer 27. 二叉树的镜像
https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
思路:
1-1 | 辅助队列的解法
利用一个辅助队列, 首先放入根节点, 然后一层一层的交换左右节点即可
1-2 | 递归的解法
边界条件: 节点为空
利用递归不断交换左右节点
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:
TreeNode* mirrorTree(TreeNode* root) {
return aux(root);
}
TreeNode* aux(TreeNode* root) {
if (root == nullptr) return root;
queue<TreeNode*> q; q.push(root);
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
TreeNode* t = node->left;
node->left = node->right;
node->right = t;
}
return root;
}
TreeNode* recursion(TreeNode* root) {
if (root == nullptr) return root;
TreeNode* t = root->left;
root->left = recursion(root->right);
root->right = recursion(t);
return root;
}
};
|
2 | 剑指 Offer 28. 对称的二叉树
https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
上题是针对节点进行二叉树的镜像翻转的
本题是判断节点的值是否对称
思路:
2-1 | dfs(自顶向下的)
如果一个二叉树:
- 右子节点的右子节点的值 == 左子节点的左子节点的值
- 左子节点的右子节点的值 == 右子节点的左子节点的值
那么这个二叉树是对称的
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
|
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
else return dfs(root->left, root->right);
}
bool dfs(TreeNode* left, TreeNode* right) {
if (left == nullptr && right == nullptr) return true;
else if (left == nullptr || right == nullptr) return false;
return (left->val == right->val && (dfs(left->left, right->right) && dfs(left->right, right->left)));
}
};
|
2-2 | 按层广搜(bfs)
没想到递归首先想到的思路, nullptr的val用-1代替, 然后每次将该层的val对半处理, 利用栈进行匹配.
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
| class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
queue<TreeNode*> q; q.push(root);
while (!q.empty()) {
int sz = q.size();
int mid = sz / 2;
stack<int> s;
while (sz > mid) {
TreeNode* x = q.front(); q.pop();
if (x != nullptr) {
q.push(x->left); q.push(x->right);
s.push(x->val);
} else {
s.push(-1);
}
sz--;
}
while (sz) {
TreeNode* x = q.front(); q.pop();
if (x != nullptr) {
q.push(x->left); q.push(x->right);
int cmp = s.top(); s.pop();
if (cmp != x->val) return false;
} else {
int cmp = s.top(); s.pop();
if (cmp != -1) return false;
}
sz--;
}
}
return true;
}
};
|
3 | 剑指 Offer 32 - II. 从上到下打印二叉树 II
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
same: 剑指 Offer 32 - I. 从上到下打印二叉树
层序遍历二叉树可以用队列的形式, 这题的关键在于, 队列的长度是不断变化的(一边push一边pop), 如何确定每一层元素个数?
——可以在每次打印前保存当前队列的大小sz
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> ans;
queue<TreeNode*> q; q.push(root);
while (!q.empty()) {
int sz = q.size();
vector<int> res;
while (sz--) {
TreeNode* x = q.front(); q.pop();
if (x) {
res.push_back(x->val);
q.push(x->left);
q.push(x->right);
}
}
if (!res.empty())
ans.push_back(res);
}
return ans;
}
};
|
4 | 剑指 Offer 55 - II. 平衡二叉树
https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
平衡二叉树: 二叉树中任意节点的左右子树的深度相差不超过1
4-1 | 复杂度较高的方式: 先序遍历 (自顶向下)
利用一个cnt函数计算每一个结点的深度, 然后对每一个结点都确认一下是否满足平衡二叉树的条件
一个二叉树的深度 = 1 + max(左左子树深度, 右子树深度)
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
bool isBalanced(TreeNode* root) {
if (!root) return true;
return (abs(cnt(root->left) - cnt(root->right)) <= 1) && isBalanced(root->left) && isBalanced(root->right);
}
int cnt (TreeNode* root) {
if (root == nullptr) return 0;
return max(cnt(root->left), cnt(root->right)) + 1;
}
};
|
4-2 | 复杂度较低的方式: 后序遍历 (自底向上)
可以发现自顶向下的方式在计算高层结点的时候每次都会重新计算低层结点的深度, 造成了大量的重复计算, 可以利用递归的方式自底向上进行判断
当底层的子树不满足平衡二叉树条件时可以直接退出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
bool isBalanced(TreeNode* root) {
return recur(root) != -1 ? true : false;
}
int recur(TreeNode* root) {
if (!root) return 0;
int dl = recur(root->left), dr = recur(root->right);
if (dl == -1 || dr == -1) return -1;
if (abs(dl - dr) <= 1) return max(dl, dr) + 1;
return -1;
}
};
|
5 | 剑指 Offer 68 - II. 二叉树的最近公共祖先
https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
自底向上, 当:
p, q分居结点左右两侧时, 该结点就是p, q的最近公共祖先
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) return root;
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if (l != nullptr && r != nullptr) return root;
else if (l != nullptr) return l;
else return r;
}
};
|
6 | 剑指 Offer 54. 二叉搜索树的第k大节点
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
对于一个二叉搜索树, 有如下性质:
二叉搜索树的中序遍历结果是升序的数组
故, 如果对于每一个结点, 将中序规则改成先右后左, 则遍历结果为降序数组, 这样第k个遍历的结点就是第k大结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int res, k;
int kthLargest(TreeNode* root, int k) {
this->k = k;
dfs(root);
return res;
}
void dfs(TreeNode* root) {
if (!root) return;
dfs(root->right);
k--;
if (k == 0) res = root->val;
dfs(root->left);
}
};
|
注意这里有一个错误不要犯:
由于这里的k是局部变量, 这样在递归时后面改变的k不会影响前面的k值, 所以造成结果的错误
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int res;
int kthLargest(TreeNode* root, int k) {
dfs(root, k);
return res;
}
void dfs(TreeNode* root, int k) {
if (!root) return;
dfs(root->right, k);
k--;
if (k == 0) res = root->val;
dfs(root->left, k);
}
};
|