二叉树的先序遍历
根 -> 左 -> 右
参考代码
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
/**
* 递归版本
*/
vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
void dfs(TreeNode* root){
if(!root) return;
res.push_back(root->val);
dfs(root->left);
dfs(root->right);
}
/**
* 非递归版本
*/
vector<int> preorderTraversal(TreeNode* root){
vector<int> res;
if (!root) return res;
stack<TreeNode*> stk;
stk.push(root);
while(stk.size()){
auto node = stk.top();
stk.pop();
res.push_back(node->val);
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}
return res;
}
二叉树的中序遍历
左 -> 根 -> 右
参考代码
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
/**
* 递归版本
*/
vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
void dfs(TreeNode* root){
if (!root) return;
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
}
/**
* 非递归版本
*/
vector<int> inorderTraversal(TreeNode* root){
vector<int> res;
stack<TreeNode*> stk;
while (root || stk.size()){
while (root){
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
二叉树的后序遍历
左 -> 右 -> 根
参考代码
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
40
41
42
43
44
45
46
/**
* 递归版本
*/
vector<int> res;
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
void dfs(TreeNode* root){
if (!root) return;
dfs(root->left);
dfs(root->right);
res.push_back(root->val);
}
/**
* 非递归版本
*/
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
if (!root) return res;
auto cur = root;
TreeNode* pre = nullptr;
while (cur){ // 左孩子
stk.push(cur);
cur = cur->left;
}
while (stk.size()){
cur = stk.top();
// 当当前结点的右孩子为空，或右孩子已经访问过了，则当前结点可以访问
if (!(cur->right) || cur->right == pre){
res.push_back(cur->val);
pre = cur;
stk.pop();
} else { // 遍历右孩子
cur = cur->right;
while (cur){
stk.push(cur);
cur = cur->left;
}
}
}
return res;
}
二叉树的层序遍历
从上到下一层一层遍历
参考代码
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
40
41
/**
* 非递归版本 队列
*/
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while(q.size()){
vector<int> t;
int len = q.size();
for (int i = 0; i < len; i++) {
auto node = q.front();
q.pop();
t.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(t);
}
return res;
}
/**
* 递归版本
*/
vector<vector<int>> res;
vector<vector<int>> levelOrder(TreeNode* root) {
dfs(root, 0);
return res;
}
void dfs(TreeNode* root, int level){
if (res.size() == level) { // 需要构建下一层
vector<int> t;
res.push_back(t);
}
res[level].push_back(root->val);
if (root->left) dfs(root->left, level + 1);
if (root->right) dfs(root->right, level + 1);
}
二叉树的层序遍历II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）LeetCode107
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while(q.size()){
vector<int> t;
int len = q.size();
for (int i = 0; i < len; i++) {
auto node = q.front();
q.pop();
t.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(t);
}
reverse(res.begin(), res.end()); // 这儿翻转一下即可
return res;
}
二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。LeetCode103
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
bool d = false; // 方向
while (q.size()) {
vector<int> t;
int len = q.size();
for (int i = 0; i < len; i++) {
auto node = q.front();
q.pop();
t.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
if (d) reverse(t.begin(), t.end());
res.push_back(t);
d = !d;
}
return res;
}
二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。LeetCode199
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
int len = q.size();
for (int i = 0; i < len; i++) {
auto node = q.front();
if (i == len - 1) res.push_back(node->val); // 这儿操作
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
从前序和中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。LeetCode105
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unordered_map<int, int> pos;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for (int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i;
return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
}
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){
if (pl > pr) return nullptr;
int val = preorder[pl];
int k = pos[val];
int len = k - il;
auto root = new TreeNode(val);
root->left = dfs(preorder, inorder, pl + 1, pl + len, il, k - 1);
root->right = dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir);
return root;
}
从中序和后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。LeetCode106
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unordered_map<int, int> pos;
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = inorder.size();
for(int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i;
return dfs(inorder, postorder, 0, n - 1, 0, n - 1);
}
TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr){
if(il > ir) return nullptr;
int val = postorder[pr];
int k = pos[val];
int len = k - il;
auto root = new TreeNode(val);
root->left = dfs(inorder, postorder, il, k - 1, pl, pl + len - 1);
root->right = dfs(inorder, postorder, k + 1, ir, pl + len, pr - 1);
return root;
}
二叉树的序列化和反序列化
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。LeetCode297
参考代码
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
40
41
string serialize(TreeNode* root){
string res;
dfs1(root, res);
return res;
}
void dfs1(TreeNode* root, string& res){
if(!root){
res += "#,";
return;
}
res += to_string(root->val) + ',';
dfs1(root->left, res);
dfs1(root->right, res);
}
TreeNode* deserialize(string data){
return dfs2(data, 0);
}
void dfs2(string& data, int& idx){
if(data[idx] == '#'){
idx++;
return nullptr;
}
int t = 0;
bool is_minus = false;
if(data[idx] == '-') {
is_minus = true;
idx++;
}
while(data[idx] != ','){
t = t * 10 + data[idx] - '0';
idx++;
}
idx++;
auto root = new TreeNode(t);
root->left = dfs2(data, idx);
root->right = dfs2(data, idx);
return root;
}
二叉树的镜像
翻转(镜像)一棵二叉树。LeetCode226
参考代码
1
2
3
4
5
6
7
TreeNode* invertTree(TreeNode* root){
if (!root) return root;
auto t = root->left;
root->left = invertTree(root->right);
root->right = invertTree(t);
return root;
}
对称二叉树
给定一个二叉树，检查它是否是镜像对称的。LeetCode101
参考代码
1
2
3
4
5
6
7
8
9
10
bool isSymmetric(TreeNode* root){
return dfs(root, root);
}
bool dfs (TreeNode* r1, TreeNode* r2) {
if(!r1 && !r2) return true;
if(!r1 || !r2) return false;
if(r1->val != r2->val) return false;
return dfs(r1->left, r2->right) && dfs(r1->right, r2->left);
}
二叉树的最大深度
给定一个二叉树，找出其最大深度。LeetCode104
参考代码
1
2
3
4
5
6
int maxDepth(TreeNode* root) {
if (!root) return 0;
int l = maxDepth(root->left);
int r = maxDepth(root->right);
return max(l, r) + 1;
}
二叉树的最小深度
给定一个二叉树，找出其最小深度。LeetCode111
参考代码
1
2
3
4
5
6
7
8
int minDepth(TreeNode* root) {
if (!root) return 0;
int l = minDepth(root->left);
int r = minDepth(root->right);
// 都为空时，说明当前结点是叶结点，返回1，否则为非空结点+1
if (!(root->left) || !(root->right)) return l + r + 1;
return min(l, r) + 1;
}
平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。LeetCode110
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isBalanced(TreeNode* root) {
if (!root) return true;
int l = dfs(root->left);
int r = dfs(root->right);
return abs(l - r) < 2 && isBalanced(root->left) && isBalanced(root->right);
}
int dfs(TreeNode* root) {
if (!root) return 0;
int l = dfs(root->left);
int r = dfs(root->right);
return max(l, r) + 1;
}
二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。LeetCode543
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int res = 0;
// 枚举所有最高点
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return res;
}
int dfs(TreeNode* root) {
if (!root) return 0;
auto left = dfs(root->left);
auto right = dfs(root->right);
// 左边最长路径+右边最长路径
res = max(res, left + right);
return max(left + 1, right + 1);
}
二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。LeetCode124
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int res = INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return res;
}
int dfs(TreeNode* root) {
if (!root) return 0;
auto left = dfs(root->left);
auto right = dfs(root->right);
// 左边最大值+右边最大值
res = max(res, left + root->val + right);
// 如果以当前结点为根节点的树的路径和小于0，则不要了
return max(0, root->val + max(left, right));
}
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。LeetCode236
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
// 如果以root为根的子树中包含p或q，则返回它们的最近公共祖先
// 如果只包含p，则返回p
// 如果只包含q，则返回q
// 如果都不包含，则返回null
if(!root || p == root || q == root) return root;
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
// 如果左边不包含
// 如果右边也不包含，则right为null，最终返回null
// 如果右边只包含p或q，则right=p或q，最终返回p或q
// 如果右边同时包含p或q，则right是最近公共祖先，最终返回最近公共祖先。
if(!left) return right;
if(!right) return left;
// 如果左右两边都不为null，说明左右两边各包含一个，此时当前结点是最近公共祖先
return root;
}
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。LeetCode235
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 根据定义：以root最低公共祖先的情况有三种
* 1.p和q在root的子树中，并且p和q在root的两侧
* 2.p=root,且q在root的左或右子树中
* 3.q=root，且p在root的左或右子树中
*
* 注意二叉搜索树的性质，可以优化
*/
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root; // 第23种情况
if (root->val < p->val && root->val < q->val) // p和q都在右子树
return lowestCommonAncestor(root->right, p, q);
if (root->val > p->val && root->val > q->val) // p和q都在左子树
return lowestCommonAncestor(root->left, p, q);
return root; // p和q在两侧
}
二叉树展开为链表
给定一个二叉树，原地将它展开为一个单链表。LeetCode114
参考代码
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
TreeNode *pre = nullptr; // 记录当前结点右子树展开的链表的头结点
/**
* 递归版本
* 后序遍历反过来了
*/
void flatten(TreeNode *root) {
if (!root) return;
flatten(root->right);
flatten(root->left);
root->right = pre; // 当前结点的右指针设置为右子树展开的链表的头结点
root->left = nullptr; // 左子树置空
pre = root; // 更新头结点
}
/**
* 非递归版
*/
void flatten(TreeNode *root) {
while (root) {
if (root->left) {
//寻找当前结点左子树中的最右结点
auto right = root->left;
while (right->right) {
right = right->right;
}
// 最右结点指向当前结点的右子树
right->right = root->right;
// 当前结点的右子树设置为当前结点的左子树
root->right = root->left;
// 当前结点的左子树置空
root->left = nullptr;
}
root = root->right;
}
}
二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。LeetcCode426
参考代码
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
Node* pre = nullptr; // 记录前一个结点
Node* head = nullptr; //头结点
/**
* 利用二叉搜索树中序遍历的性质，
* 对于当前结点，我们先中序遍历转换其左子树，此时得到的结果就是左子树部分转换的双向链表，
* 记末尾结点为pre，则对于当前结点cur，令cur的左指针指向pre，pre的右指针指向cur，
* 更新pre为当前结点cur，然后遍历当前结点的右子树。
* 当pre为null是，此时cur为头结点
*/
Node* treeToDoublyList(Node* root) {
if (!root) return root;
dfs(root);
// 下面这两行转换成循环双向链表
head->left = pre;
pre->right = head;
return head;
}
/**
* 中序遍历
*/
void dfs(Node* cur) {
if (!cur) return;
dfs(cur->left); //先遍历左子树
if (pre) // 如果pre不为空，则连接当前结点
pre->right = cur;
else //否则，当前结点是头结点
head = cur;
cur->left = pre;
pre = cur; // 更新前一个结点为当前结点
dfs(cur->right); // 遍历右子树
}
将数组转换成二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。LeetCode108
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (!nums.size()) return nullptr;
return dfs(nums, 0, nums.size() - 1);
}
TreeNode* dfs(vector<int>& nums, int l, int r) {
if (l > r) return nullptr;
int mid = l + r >> 1;
auto root = new TreeNode(nums[mid]);
root->left = dfs(nums, l, mid - 1);
root->right = dfs(nums, mid + 1, r);
return root;
}
路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。LeetCode112
参考代码
1
2
3
4
5
6
bool hasPathSum(TreeNode* root, int sum) {
if (!root) return false;
if (!root->left && !root->right) return sum - root->val == 0;
return hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);
}
路径总和II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。LeetCode113
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> res;
/**
* 回溯法
*/
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if (!root) return res;
vector<int> path;
dfs(root, sum, path);
return res;
}
void dfs(TreeNode* root, int sum, vector<int>& path) {
if (!root) return;
path.push_back(root->val);
if (!root->left && !root->right && sum - root->val == 0)
res.push_back(path);
dfs(root->left, sum - root->val, path);
dfs(root->right, sum - root->val, path);
path.pop_back();
}
路径总和III
给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。LeetCode437
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int pathSum(TreeNode* root, int sum) {
if (!root) return 0;
auto res = dfs(root, sum);
auto l = pathSum(root->left, sum);
auto r = pathSum(root->right, sum);
return res + l + r;
}
int dfs(TreeNode* root, int sum) {
if (!root) return 0;
sum -= root->val;
auto t = sum == 0 ? 1 : 0;
return t + dfs(root->left, sum) + dfs(root->right, sum);
}
二叉搜索树中第k小(大)的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。LeetCode230
参考代码
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
int res = 0, cnt = 0;
int kthSmallest(TreeNode* root, int k) {
dfs(root, k);
return res;
}
void dfs(TreeNode* root, int k) {
if (!root) return;
dfs(root->left, k);
cnt++;
if (cnt == k) {
res = root->val;
return;
}
dfs(root->right, k);
}
// 第k大
int res = 0, cnt = 0;
int kthSmallest(TreeNode* root, int k) {
dfs(root, k);
return res;
}
void dfs(TreeNode* root, int k) {
if (!root) return;
dfs(root->right, k);
cnt++;
if (cnt == k) {
res = root->val;
return;
}
dfs(root->left, k);
}
树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)。B是A的子结构， 即 A中有出现和B相同的结构和节点值。
参考代码
1
2
3
4
5
6
7
8
9
10
bool isSubStructure(TreeNode* A, TreeNode* B){
return (A && B) && (dfs(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B));
}
bool dfs(TreeNode* p1, TreeNode* p2) {
if(!p2) return true;
if(!p1) return false;
if(p1->val != p2->val) return false;
return dfs(p1->left, p2->left) && dfs(p1->right, p2->right);
}
求根到叶结点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。LeetCode129
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int res = 0;
int sumNumbers(TreeNode* root) {
int path = 0;
dfs(root, path);
return res;
};
void dfs(TreeNode* root, int path) {
if (!root) return;
if (!root->left && !root->right) {
res += path * 10 + root->val;
return;
}
path = path * 10 + root->val;
dfs(root->left, path);
dfs(root->right, path);
}
验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。LeetCode98
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isValidBST(TreeNode* root) { return dfs(root, INT_MIN, INT_MAX); }
/**
* 相当于判断根节点的值是否在正确的区间
*/
bool dfs(TreeNode* root, long long minV, long long maxV) {
if (!root) return true;
// 如果根节点的值比最小值小或者比最大值大，说明超出了区间范围，不合法
if (root->val < minV || root->val > maxV) return false;
// 递归 缩小区间范围
return dfs(root->left, minV, root->val - 1ll) &&
dfs(root->right, root->val + 1ll, maxV);
}
不同的二叉搜索树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？LeetCode96 不懂。。。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
/**
* 思路：假设n个节点存在二叉搜索树的个数是G(n)，令f(i)表示以i为根节点的二叉搜索树，则：
* G(n) = f(1) + f(2) + ... + f(n)
* 当以i为根节点时：f(i) = G(i-1) * G(n-i),左子树有i-1个结点，右子树有n-i个结点
* 综上有：G(n) = G(0)*G*(n-1) + G(1)*G(n-2) + ... + G(n-1)*G(0) 卡特兰数
* 通过dp来实现
*/
int numTrees(int n) {
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};
不同的二叉搜索树II
给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。LeetCode95 不太懂
参考代码
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
40
41
42
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
vector<TreeNode*> res;
if (!n) return res;
return dfs(1, n);
}
// 递归 区间l，r可以组成的二叉搜索树
vector<TreeNode*> dfs(int l, int r) {
vector<TreeNode*> res;
if (l > r) {
res.push_back(nullptr);
return res;
}
if (l == r) {
auto node = new TreeNode(l);
res.push_back(node);
return res;
}
for (int i = l; i <= r; i++) {
vector<TreeNode*> leftTrees = dfs(l, i - 1); // 左区间可以组成的二叉搜索树
vector<TreeNode*> rightTrees = dfs(i + 1, r); //右区间可以组成的二叉搜索树
// 组合左右区间的所有左右子树
for (auto lt : leftTrees) {
for (auto rt : rightTrees) {
auto root = new TreeNode(i);
root->left = lt;
root->right = rt;
res.push_back(root);
}
}
}
return res;
}
};
完全二叉树的结点个数
给出一个完全二叉树，求出该树的节点个数。LeetCode222
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int countNodes(TreeNode *root) {
if (!root) return 0;
int res = 0;
queue<TreeNode *> q;
q.push(root);
while (q.size()) {
int len = q.size();
res += len;
for (int i = 0; i < len; i++) {
auto node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。LeetCode257
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<string> res;
vector<string> binaryTreePaths(TreeNode *root) {
vector<string> path;
dfs(root, path);
return res;
}
void dfs(TreeNode *root, vector<string> &path) {
if (!(root->left) && !(root->right)) {
string t;
for (auto s : path) t += s + "->";
t += to_string(root->val);
res.push_back(t);
return;
}
path.push_back(to_string(root->val));
dfs(root->left, path);
dfs(root->right, path);
path.pop_back();
}
从先序遍历还原二叉树(困难)
我们从二叉树的根节点 root 开始进行深度优先搜索。在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。如果节点只有一个子节点，那么保证该子节点为左子节点。给出遍历输出 S，还原树并返回其根节点 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
TreeNode *recoverFromPreorder(string s) {
int idx = 0;
stack<TreeNode *> stk;
while (idx < s.size()) {
int level = 0;
// 统计当前结点在第几层
while (s[idx] == '-') idx++, level++;
int t = 0;
// 当前结点的数字
while (idx < s.size() && s[idx] != '-') {
t = t * 10 + s[idx] - '0';
idx++;
}
// 构建当前结点
auto root = new TreeNode(t);
// 如果当前结点所在的层和栈的高度一样，则将栈顶元素的左子树指向当前结点
if (level == stk.size()) {
if (stk.size()) stk.top()->left = root;
// 如果当前结点所在的层和栈的高度不一样，说明当前结点是右子结点，先将栈中的左子节点弹出，再将栈顶元素的右子树指向当前结点
} else {
while (level != stk.size()) stk.pop();
stk.top()->right = root;
}
stk.push(root);
}
// 栈底元素是根节点
while (stk.size() > 1) stk.pop();
return stk.top();
}
把二叉搜索树转换为累加树(简单)
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。把二叉搜索树转换为累加树
参考代码
1
2
3
4
5
6
7
8
9
10
int pre = 0; // 记录比当前结点大的值的和
// 中序遍历倒过来
TreeNode* convertBST(TreeNode* root) {
if (!root) return root;
convertBST(root->right); // 先去右子树
root->val += pre; // 更新当前节点的值
pre = root->val; // 更新pre
convertBST(root->left); // 去左子树
return root;
}
合并二叉树(简单)
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。合并二叉树
参考代码
1
2
3
4
5
6
7
8
9
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (!t1 && !t2) return nullptr;
if (!t1) return t2;
if (!t2) return t1;
auto root = new TreeNode(t1->val + t2->val);
root->left = mergeTrees(t1->left, t2->left);
root->right = mergeTrees(t1->right, t2->right);
return root;
}
填充每个节点的下一个右侧节点指针(中等)
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。填充每个节点的下一个右侧节点指针
参考代码
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
Node* connect(Node* root) {
if (root && root->left && root->right) {
// 左节点指向右结点
root->left->next = root->right;
if (root->next) {
// 右结点指向下一个的左节点
root->right->next = root->next->left;
}
connect(root->right);
connect(root->left);
}
return root;
}
Node* connect(Node* root) {
if (root == nullptr) {
return root;
}
Node* mostLeft = root; // 控制数的层数
// 为什么是->left!=nullptr，是因为根据当前层就能连接当前层的所有孩子结点
while (mostLeft->left != nullptr) {
Node* temp = mostLeft;
// 横向遍历
while (temp != nullptr) {
// 左孩子指向右孩子
temp->left->next = temp->right;
// 当前结点的右孩子指向下一个结点的左孩子
if (temp->next != nullptr) {
temp->right->next = temp->next->left;
}
temp = temp->next; // 向右移
}
mostLeft = mostLeft->left; // 向下移
}
return root;
}
填充每个节点的下一个右侧节点指针II(中等)
给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。填充每个节点的下一个右侧节点指针II
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Node* connect(Node* root) {
// 排除没有子节点的情况
if (root && (root->left || root->right)) {
//既有做子节点又有右子节点，左节点指向右结点
if (root->left && root->right) {
root->left->next = root->right;
}
// 获得当前结点的最右侧的结点
Node* node = root->right ? root->right : root->left;
// 当前结点的同层的下一个结点
Node* head = root->next;
// 排除没有子节点的结点
while (head && (head->left == nullptr && head->right == nullptr)) {
head = head->next;
}
// 将当前结点最右边的结点的next指向下一个结点的最左边的结点
node->next =
head ? (head->left ? head->left : head->right) : nullptr;
connect(root->right);
connect(root->left);
}
return root;
}
