目录
1--递归遍历
1-1--前序遍历
1-2--中序遍历
1-3--后序遍历
2--迭代遍历
2-1--前序遍历
2-2--后序遍历
2-3--中序遍历
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--把二叉搜索树转换为累加树
1--递归遍历
1-1--前序遍历
前序遍历:根→左→右;
#include <iostream>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution{
public:
std::vector<int> preorderTraversal(TreeNode* root) {
std::vector<int> res;
dfs(root, res);
return res;
}
void dfs(TreeNode* root, std::vector<int>& res){
if(root == nullptr) return;
res.push_back(root->val);
dfs(root->left, res);
dfs(root->right, res);
}
};
int main(int argc, char* argv[]){
// root = [1, null, 2, 3]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(3);
Node1->right = Node2;
Node2->left = Node3;
Solution S1;
std::vector<int> res = S1.preorderTraversal(Node1);
for(auto item : res) std::cout << item << " ";
std::cout << std::endl;
return 0;
}
1-2--中序遍历
中序遍历:左→根→右;
#include <iostream>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution{
public:
std::vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> res;
dfs(root, res);
return res;
}
void dfs(TreeNode* root, std::vector<int>& res){
if(root == nullptr) return;
dfs(root->left, res);
res.push_back(root->val);
dfs(root->right, res);
}
};
int main(int argc, char* argv[]){
// root = [1, null, 2, 3]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(3);
Node1->right = Node2;
Node2->left = Node3;
Solution S1;
std::vector<int> res = S1.inorderTraversal(Node1);
for(auto item : res) std::cout << item << " ";
std::cout << std::endl;
return 0;
}
1-3--后序遍历
后序遍历:左→右→根;
#include <iostream>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution{
public:
std::vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> res;
dfs(root, res);
return res;
}
void dfs(TreeNode* root, std::vector<int>& res){
if(root == nullptr) return;
dfs(root->left, res);
dfs(root->right, res);
res.push_back(root->val);
}
};
int main(int argc, char* argv[]){
// root = [1, null, 2, 3]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(3);
Node1->right = Node2;
Node2->left = Node3;
Solution S1;
std::vector<int> res = S1.postorderTraversal(Node1);
for(auto item : res) std::cout << item << " ";
std::cout << std::endl;
return 0;
}
2--迭代遍历
2-1--前序遍历
基于栈结构,先将根节点入栈,再将节点从栈中弹出,如果节点的右孩子不为空,则右孩子入栈;如果节点的左孩子不为空,则左孩子入栈;
循环出栈处理节点,并将右孩子和左孩子存在栈中(右孩子先进栈,左孩子再进栈,因为栈先进后出,这样可以确保左孩子先出栈,符合根→左→右的顺序);
#include <iostream>
#include <vector>
#include <stack>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution{
public:
std::vector<int> preorderTraversal(TreeNode* root) {
std::vector<int> res;
if(root == nullptr) return res;
std::stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode *tmp = stk.top();
stk.pop();
res.push_back(tmp->val);
if(tmp->right != nullptr) stk.push(tmp->right); // 右
if(tmp->left != nullptr) stk.push(tmp->left); // 左
}
return res;
}
};
int main(int argc, char* argv[]){
// root = [1, null, 2, 3]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(3);
Node1->right = Node2;
Node2->left = Node3;
Solution S1;
std::vector<int> res = S1.preorderTraversal(Node1);
for(auto item : res) std::cout << item << " ";
std::cout << std::endl;
return 0;
}
2-2--后序遍历
可以使用两个栈来实现,一个是遍历栈,一个是收集栈,参考之前的笔记:后序遍历的迭代实现
也可以类似于前序遍历,基于一个栈实现,只不过需要改变入栈顺序:每出栈处理一个节点,其左孩子入栈,再右孩子入栈;此时处理顺序为:根->右->左,最后将结果 reverse 即可;
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution{
public:
std::vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> res;
if(root == nullptr) return res;
std::stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode* tmp = stk.top();
stk.pop();
if(tmp->left != nullptr) stk.push(tmp->left);
if(tmp->right != nullptr) stk.push(tmp->right);
res.push_back(tmp->val);
}
// 反转
std::reverse(res.begin(), res.end());
return res;
}
};
int main(int argc, char* argv[]){
// root = [1, null, 2, 3]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(3);
Node1->right = Node2;
Node2->left = Node3;
Solution S1;
std::vector<int> res = S1.postorderTraversal(Node1);
for(auto item : res) std::cout << item << " ";
std::cout << std::endl;
return 0;
}
2-3--中序遍历
基于栈结构,初始化一个栈,根节点入栈;
①:左子结点全部入栈;
②:结点出栈,处理结点;
③:对出栈结点的右子树重复执行第 ① 步操作;
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution{
public:
std::vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> res;
if(root == nullptr) return res;
std::stack<TreeNode*> stk;
while(!stk.empty() || root != nullptr){
if(root != nullptr){ // 左子结点全部入栈
stk.push(root);
root = root->left;
}
else{
TreeNode *tmp = stk.top();
stk.pop();
res.push_back(tmp->val);
// 出栈节点的右孩子执行相同操作
root = tmp->right;
}
}
return res;
}
};
int main(int argc, char* argv[]){
// root = [1, null, 2, 3]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(3);
Node1->right = Node2;
Node2->left = Node3;
Solution S1;
std::vector<int> res = S1.inorderTraversal(Node1);
for(auto item : res) std::cout << item << " ";
std::cout << std::endl;
return 0;
}
3--二叉树的层序遍历
主要思路:
经典广度优先搜索,基于队列;
对于本题需要将同一层的节点放在一个数组中,因此遍历的时候需要用一个变量 nums 来记录当前层的节点数,即 nums 等于队列元素的数目;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::vector<std::vector<int>> res;
if(root == nullptr) return res;
std::queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int nums = q.size(); // 当前层的节点数
std::vector<int> tmp;
while(nums > 0){ // 遍历处理同一层
TreeNode *cur = q.front();
q.pop();
tmp.push_back(cur->val);
if(cur->left != nullptr) q.push(cur->left);
if(cur->right != nullptr) q.push(cur->right);
nums--;
}
res.push_back(tmp); // 记录当前层的元素
}
return res;
}
};
int main(int argc, char* argv[]){
// root = [1, null, 2, 3]
TreeNode *Node1 = new TreeNode(3);
TreeNode *Node2 = new TreeNode(9);
TreeNode *Node3 = new TreeNode(20);
TreeNode *Node4 = new TreeNode(15);
TreeNode *Node5 = new TreeNode(7);
Node1->left = Node2;
Node1->right = Node3;
Node3->left = Node4;
Node3->right = Node5;
Solution S1;
std::vector<std::vector<int>> res = S1.levelOrder(Node1);
for(auto item : res) {
for (int v : item) std::cout << v << " ";
std::cout << std::endl;
}
return 0;
}
4--翻转二叉树
主要思路:
递归交换左右子树;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
reverse(root);
return root;
}
void reverse(TreeNode *root){
if(root == nullptr) return;
reverse(root->left);
reverse(root->right);
TreeNode *tmp = root->left;
root->left = root->right;
root->right = tmp;
}
};
// 层次遍历打印
void PrintTree(TreeNode *root){
std::queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
TreeNode *tmp = q.front();
q.pop();
std::cout << tmp->val << " ";
if(tmp->left != nullptr) q.push(tmp->left);
if(tmp->right != nullptr) q.push(tmp->right);
}
}
int main(int argc, char* argv[]){
// root = [4,2,7,1,3,6,9]
TreeNode *Node1 = new TreeNode(4);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(7);
TreeNode *Node4 = new TreeNode(1);
TreeNode *Node5 = new TreeNode(3);
TreeNode *Node6 = new TreeNode(6);
TreeNode *Node7 = new TreeNode(9);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Node3->left = Node6;
Node3->right = Node7;
Solution S1;
TreeNode *res = S1.invertTree(Node1);
PrintTree(res);
}
5--对称二叉树
主要思路:
递归判断左树的左子树是否与右数的右子树相等,左树的右子树是否与右树的左子树相等;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return true;
bool res = dfs(root->left, root->right);
return res;
}
bool dfs(TreeNode *left, TreeNode *right){
if((left != nullptr && right == nullptr) ||
(left == nullptr && right != nullptr)) return false;
if(left == nullptr && right == nullptr) return true;
if (left->val != right->val) return false;
bool isSame1 = dfs(left->left, right->right);
bool isSame2 = dfs(left->right, right->left);
return isSame1 && isSame2;
}
};
int main(int argc, char* argv[]){
// root = [4,2,7,1,3,6,9]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(2);
TreeNode *Node4 = new TreeNode(3);
TreeNode *Node5 = new TreeNode(4);
TreeNode *Node6 = new TreeNode(4);
TreeNode *Node7 = new TreeNode(3);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Node3->left = Node6;
Node3->right = Node7;
Solution S1;
bool res = S1.isSymmetric(Node1);
if(res) std::cout << "true" << std::endl;
else std::cout << "false" << std::endl;
}
6--二叉树最大深度
主要思路:
递归计算左右子树的深度,选取两者最大值 +1 返回;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
int res = dfs(root);
return res;
}
int dfs(TreeNode* root){
if(root == nullptr) return 0;
int left_height = dfs(root->left);
int right_height = dfs(root->right);
int cur_height = std::max(left_height, right_height) + 1;
return cur_height;
}
};
int main(int argc, char* argv[]){
// root = [3,9,20,null,null,15,7]
TreeNode *Node1 = new TreeNode(3);
TreeNode *Node2 = new TreeNode(9);
TreeNode *Node3 = new TreeNode(20);
TreeNode *Node4 = new TreeNode(15);
TreeNode *Node5 = new TreeNode(7);
Node1->left = Node2;
Node1->right = Node3;
Node3->left = Node4;
Node3->right = Node5;
Solution S1;
int res = S1.maxDepth(Node1);
std::cout << res << std::endl;
return 0;
}
7--二叉树的最小深度
主要思路:
与上题有点类似,递归返回最小深度即可,但需要剔除根节点一个子树为空的情况;
对于一个根节点,其中一个子树为空,则其最小深度是不为空的子树的深度;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == nullptr) return 0;
return dfs(root);
}
int dfs(TreeNode *root){
if(root == nullptr) return 0;
// 剔除两种情况
if(root->left == nullptr) return dfs(root->right) + 1;
else if(root->right == nullptr) return dfs(root->left) + 1;
else{
int left_height = dfs(root->left);
int right_height = dfs(root->right);
int cur_min_height = std::min(left_height, right_height) + 1;
return cur_min_height;
}
}
};
int main(int argc, char* argv[]){
// root = [3,9,20,null,null,15,7]
TreeNode *Node1 = new TreeNode(3);
TreeNode *Node2 = new TreeNode(9);
TreeNode *Node3 = new TreeNode(20);
TreeNode *Node4 = new TreeNode(15);
TreeNode *Node5 = new TreeNode(7);
Node1->left = Node2;
Node1->right = Node3;
Node3->left = Node4;
Node3->right = Node5;
Solution S1;
int res = S1.minDepth(Node1);
std::cout << res << std::endl;
return 0;
}
8--完全二叉树节点的数量
主要思路:
普通二叉树可以通过层次遍历来统计节点数目;
对于本题中的完全二叉树,可以通过 2**k - 1 的公式来计算二叉树节点的数目;
首先需判断一个子树是否为完全二叉树,如果是则通过上式计算;如果不是完全二叉树,则对于当前子树,需要分别向左右子树递归计算其节点数目(相当于获取信息),最后将结果相加(相当于处理信息),并加上1返回即可;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == nullptr) return 0;
return dfs(root);
}
int dfs(TreeNode *root){
if(root == nullptr) return 0;
TreeNode *left = root->left, *right = root->right;
int left_height = 0, right_height = 0;
while(left != nullptr){
left = left->left;
left_height++;
}
while(right != nullptr){
right = right->right;
right_height++;
}
if(left_height == right_height) return (2<<left_height) - 1; // 满二叉树
int left_nums = dfs(root->left);
int right_nums = dfs(root->right);
return left_nums + right_nums + 1;
}
};
int main(int argc, char* argv[]){
// root = [1,2,3,4,5,6]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(3);
TreeNode *Node4 = new TreeNode(4);
TreeNode *Node5 = new TreeNode(5);
TreeNode *Node6 = new TreeNode(6);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Node3->left = Node6;
Solution S1;
int res = S1.countNodes(Node1);
std::cout << res << std::endl;
return 0;
}
9--平衡二叉树
主要思路:
通过高度差不大于1,来递归判断子树是否是平衡二叉树,不是则返回-1,是则返回对应的高度;
#include <iostream>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root == nullptr) return true;
int height = dfs(root);
return height == -1 ? false : true;
}
int dfs(TreeNode *root){
if(root == nullptr) return 0;
int left_height = dfs(root->left);
if(left_height == -1) return -1;
int right_height = dfs(root->right);
if(right_height == -1) return -1;
if(std::abs(left_height - right_height) > 1) return -1;
else return std::max(left_height, right_height) + 1;
}
};
int main(int argc, char* argv[]){
// root = [3,9,20,null,null,15,7]
TreeNode *Node1 = new TreeNode(3);
TreeNode *Node2 = new TreeNode(9);
TreeNode *Node3 = new TreeNode(20);
TreeNode *Node4 = new TreeNode(15);
TreeNode *Node5 = new TreeNode(7);
Node1->left = Node2;
Node1->right = Node3;
Node3->left = Node4;
Node3->right = Node5;
Solution S1;
bool res = S1.isBalanced(Node1);
if(res) std::cout << "true" << std::endl;
else std::cout << "false" << std::endl;
return 0;
}
10--二叉树的所有路径
主要思路:
递归记录路径;
#include <iostream>
#include <vector>
#include <string>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
std::vector<std::string> binaryTreePaths(TreeNode* root) {
std::vector<std::string> res;
if(root == nullptr) return res;
std::string path = "";
dfs(root, res, path);
return res;
}
void dfs(TreeNode *root, std::vector<std::string>& res, std::string path){
if(root == nullptr) return;
path += std::to_string(root->val);
if(root->left == nullptr && root->right == nullptr) { // 叶子节点,回收路径
res.push_back(path);
return;
}
else path += "->";
dfs(root->left, res, path);
dfs(root->right, res, path);
}
};
int main(int argc, char* argv[]){
// root = [1,2,3,null,5]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(3);
TreeNode *Node4 = new TreeNode(5);
Node1->left = Node2;
Node1->right = Node3;
Node2->right = Node4;
Solution S1;
std::vector<std::string> res = S1.binaryTreePaths(Node1);
for(auto path : res) std::cout << path << std::endl;
return 0;
}
11--左叶子之和
主要思路:
递归到叶子节点的上一层,返回其左叶子之和;
#include <iostream>
#include <vector>
#include <string>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root == nullptr) return 0;
return dfs(root);
}
int dfs(TreeNode* root){
if(root == nullptr) return 0;
if(root->left == nullptr && root->right == nullptr) return 0;
int sum = 0;
if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr){
sum = root->left->val;
}
int left = dfs(root->left);
int right = dfs(root->right);
return left + right + sum;
}
};
int main(int argc, char* argv[]){
// root = [3,9,20,null,null,15,7]
TreeNode *Node1 = new TreeNode(3);
TreeNode *Node2 = new TreeNode(9);
TreeNode *Node3 = new TreeNode(20);
TreeNode *Node4 = new TreeNode(15);
TreeNode *Node5 = new TreeNode(7);
Node1->left = Node2;
Node1->right = Node3;
Node3->left = Node4;
Node3->right = Node5;
Solution S1;
int res = S1.sumOfLeftLeaves(Node1);
std::cout << res << std::endl;
return 0;
}
12--找树左下角的值
主要思路:
递归到最大深度层,优先返回最左边的节点值,即递归时优先搜索左子树;
#include <iostream>
#include <vector>
#include <limits.h>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
if(root == nullptr) return 0;
int max_height = INT_MIN;
int result = 0;
dfs(root, 0, max_height, result);
return result;
}
void dfs(TreeNode* root, int curheight, int& max_height, int& res){
if(root == nullptr) return;
if(root->left == nullptr && root->right == nullptr){ // 叶子节点
if(curheight + 1 > max_height){
max_height = curheight + 1;
res = root->val;
return;
}
}
dfs(root->left, curheight+1, max_height, res);
dfs(root->right, curheight+1, max_height, res);
}
};
int main(int argc, char* argv[]){
// root = [3,9,20,null,null,15,7]
TreeNode *Node1 = new TreeNode(2);
TreeNode *Node2 = new TreeNode(1);
TreeNode *Node3 = new TreeNode(3);
Node1->left = Node2;
Node1->right = Node3;
Solution S1;
int res = S1.findBottomLeftValue(Node1);
std::cout << res << std::endl;
return 0;
}
13--路径总和
主要思路:
递归搜索,判断路径和是否等于目标值即可;
#include <iostream>
#include <vector>
#include <limits.h>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr) return false;
return dfs(root, targetSum);
}
bool dfs(TreeNode* root, int targetSum){
if(root == nullptr) return false;
if(root->left == nullptr && root->right == nullptr && targetSum == root->val){
return true;
}
bool left = dfs(root->left, targetSum - root->val);
if(left) return true;
bool right = dfs(root->right, targetSum - root->val);
if(right) return true;
return false;
}
};
int main(int argc, char* argv[]){
// root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
TreeNode *Node1 = new TreeNode(5);
TreeNode *Node2 = new TreeNode(4);
TreeNode *Node3 = new TreeNode(8);
TreeNode *Node4 = new TreeNode(11);
TreeNode *Node5 = new TreeNode(13);
TreeNode *Node6 = new TreeNode(4);
TreeNode *Node7 = new TreeNode(7);
TreeNode *Node8 = new TreeNode(2);
TreeNode *Node9 = new TreeNode(1);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node3->left = Node5;
Node3->right = Node6;
Node4->left = Node7;
Node4->right = Node8;
Node6->right = Node9;
int target = 22;
Solution S1;
bool res = S1.hasPathSum(Node1, target);
if(res) std::cout << "True" << std::endl;
else std::cout << "false" << std::endl;
return 0;
}
14--从中序与后序遍历序列构造二叉树
主要思路:
中序遍历的顺序为:左→根→右,后序遍历的顺序为:左→右→根;即后序遍历的最后一个节点是根节点,因此可以根据根节点来划分中序遍历,将其划分为左子树和右子树,再根据左右子树的大小来划分后序遍历,递归构建二叉树;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
TreeNode *root = dfs(inorder, postorder);
return root;
}
TreeNode* dfs(std::vector<int>& inorder, std::vector<int>& postorder){
if(postorder.size() == 0) return nullptr;
TreeNode *root = new TreeNode(postorder[postorder.size() - 1]); // 根节点
if(postorder.size() == 1) return root;
// 划分中序遍历
int idx;
for(idx = 0; idx < inorder.size(); idx++){
if(inorder[idx] == root->val) break; // 找到中序遍历的根节点
}
// 划分后序遍历
std::vector<int> left_inorder(inorder.begin(), inorder.begin()+idx); // 左子树的中序
std::vector<int> right_inorder(inorder.begin()+idx+1, inorder.end()); // 右子树的中序
std::vector<int> left_postorder(postorder.begin(), postorder.begin() + left_inorder.size()); // 左子树的后序
std::vector<int> right_postorder(postorder.begin() + left_inorder.size(), postorder.end() - 1); // 右子树的后序
root->left = dfs(left_inorder, left_postorder);
root->right = dfs(right_inorder, right_postorder);
return root;
}
};
int main(int argc, char* argv[]){
// inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
std::vector<int> inorder = {9, 3, 15, 20, 7};
std::vector<int> postorder = {9, 15, 7, 20, 3};
Solution S1;
TreeNode *root = S1.buildTree(inorder, postorder);
// 层次遍历
std::queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode *tmp = q.front();
q.pop();
std::cout << tmp->val << " ";
if(tmp->left != nullptr) q.push(tmp->left);
if(tmp->right != nullptr) q.push(tmp->right);
}
std::cout << std::endl;
return 0;
}
15--最大二叉树
主要思路:
递归构建二叉树,首先寻找数组中的最大值,根据最大值划分左子树和右子树,递归构建左子树和右子树;
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* constructMaximumBinaryTree(std::vector<int>& nums) {
TreeNode *root = dfs(nums);
return root;
}
TreeNode* dfs(std::vector<int>& nums){
if(nums.size() == 1){
TreeNode* root = new TreeNode(nums[0]);
return root;
}
// 遍历寻找最大值
int max_idx = 0, max_value = INT_MIN;
for(int i = 0; i < nums.size(); i++){
if(nums[i] > max_value) {
max_value = nums[i];
max_idx = i;
}
}
TreeNode *root = new TreeNode(nums[max_idx]);
if(max_idx > 0){
std::vector<int> left_nums(nums.begin(), nums.begin() + max_idx);
root->left = dfs(left_nums);
}
if(max_idx < nums.size() - 1){
std::vector<int> right_nums(nums.begin() + max_idx + 1, nums.end());
root->right = dfs(right_nums);
}
return root;
}
};
int main(int argc, char* argv[]){
// nums = [3,2,1,6,0,5]
std::vector<int> nums = {3, 2, 1, 6, 0, 5};
Solution S1;
TreeNode *root = S1.constructMaximumBinaryTree(nums);
// 层次遍历
std::queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode *tmp = q.front();
q.pop();
std::cout << tmp->val << " ";
if(tmp->left != nullptr) q.push(tmp->left);
if(tmp->right != nullptr) q.push(tmp->right);
}
std::cout << std::endl;
return 0;
}
16--合并二叉树
主要思路:
递归构建二叉树,两颗子树均不为 null 时,则构建新节点,其值为传入的两根节点之和;
当其中一颗子树为空时,返回另一颗子树;
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return dfs(root1, root2);
}
TreeNode* dfs(TreeNode* root1, TreeNode* root2){
if(root1 == nullptr) return root2;
if(root2 == nullptr) return root1;
TreeNode *root = new TreeNode(root1->val + root2->val);
root->left = dfs(root1->left, root2->left);
root->right = dfs(root1->right, root2->right);
return root;
}
};
int main(int argc, char* argv[]){
// root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
TreeNode* Node1_1 = new TreeNode(1);
TreeNode* Node1_2 = new TreeNode(3);
TreeNode* Node1_3 = new TreeNode(2);
TreeNode* Node1_4 = new TreeNode(5);
Node1_1->left = Node1_2;
Node1_1->right = Node1_3;
Node1_2->left = Node1_4;
TreeNode* Node2_1 = new TreeNode(2);
TreeNode* Node2_2 = new TreeNode(1);
TreeNode* Node2_3 = new TreeNode(3);
TreeNode* Node2_4 = new TreeNode(4);
TreeNode* Node2_5 = new TreeNode(7);
Node2_1->left = Node2_2;
Node2_1->right = Node2_3;
Node2_2->right = Node2_4;
Node2_3->right = Node2_5;
Solution S1;
TreeNode *root = S1.mergeTrees(Node1_1, Node2_1);
// 层次遍历
std::queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode *tmp = q.front();
q.pop();
std::cout << tmp->val << " ";
if(tmp->left != nullptr) q.push(tmp->left);
if(tmp->right != nullptr) q.push(tmp->right);
}
std::cout << std::endl;
return 0;
}
17--二叉搜索树中的搜索
主要思路:
根据节点大小,递归从左子树或者右子树寻找;
#include <iostream>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
return dfs(root, val);
}
TreeNode* dfs(TreeNode* root, int val){
if(root == nullptr || root->val == val) return root;
if(root->val > val){
return dfs(root->left, val);
}
else return dfs(root->right, val);
}
};
int main(int argc, char* argv[]){
// root = [4,2,7,1,3], val = 2
TreeNode *Node1 = new TreeNode(4);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(7);
TreeNode *Node4 = new TreeNode(1);
TreeNode *Node5 = new TreeNode(3);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
int val = 2;
Solution S1;
TreeNode *res = S1.searchBST(Node1, val);
if(res == nullptr) std::cout << "" << std::endl;
else std::cout << res->val << std::endl;
return 0;
}
18--验证二叉搜索树
主要思路:
递归判断,确保自下而上左子树节点都小于根节点,右子树节点都大于根节点;
#include <iostream>
#include <limits.h>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
bool isValidBST(TreeNode* root) {
long long max_value = LONG_MAX, min_value = LONG_MIN;
return dfs(root, max_value, min_value);
}
bool dfs(TreeNode *root, long long max_value, long long min_value){
if(root == nullptr) return true;
if(root->val >= max_value || root->val <= min_value) return false;
bool left = dfs(root->left, root->val, min_value);
bool right = dfs(root->right, max_value, root->val);
return left && right;
}
};
int main(int argc, char* argv[]){
// root = [2, 1, 3]
TreeNode *Node1 = new TreeNode(2);
TreeNode *Node2 = new TreeNode(1);
TreeNode *Node3 = new TreeNode(3);
Node1->left = Node2;
Node1->right = Node3;
Solution S1;
bool res = S1.isValidBST(Node1);
if(res) std::cout << "true" << std::endl;
else std::cout << "false" << std::endl;
return 0;
}
19--二叉搜索树的最小绝对差
主要思路1:
利用中序遍历将二叉搜索树的元素存放在一个递增的数组中,然后遍历递增数组,计算相邻两节点的差值即可;
#include <iostream>
#include <limits.h>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
std::vector<int> res;
int min = INT_MAX;
dfs(root, res);
for(int i = 1; i < res.size(); i++){
if(res[i] - res[i-1] < min){
min = res[i] - res[i-1];
}
}
return min;
}
void dfs(TreeNode *root, std::vector<int> &res){
if(root == nullptr) return;
dfs(root->left, res);
res.push_back(root->val);
dfs(root->right, res);
}
};
int main(int argc, char* argv[]){
// root = [4,2,6,1,3]
TreeNode *Node1 = new TreeNode(4);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(6);
TreeNode *Node4 = new TreeNode(1);
TreeNode *Node5 = new TreeNode(3);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Solution S1;
int res = S1.getMinimumDifference(Node1);
std::cout << res << std::endl;
return 0;
}
主要思路2:
利用双指针递归,记录中序遍历的前一个节点和当前节点,计算两个节点的差值,并更新最小值即可;
#include <iostream>
#include <limits.h>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
dfs(root);
return min;
}
void dfs(TreeNode *cur){
if(cur == nullptr) return;
dfs(cur->left);
if(pre != nullptr){
min = std::min(min, cur->val - pre->val);
}
pre = cur;
dfs(cur->right);
}
private:
int min = INT_MAX;
TreeNode *pre = nullptr;
};
int main(int argc, char* argv[]){
// root = [4,2,6,1,3]
TreeNode *Node1 = new TreeNode(4);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(6);
TreeNode *Node4 = new TreeNode(1);
TreeNode *Node5 = new TreeNode(3);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Solution S1;
int res = S1.getMinimumDifference(Node1);
std::cout << res << std::endl;
return 0;
}
20--二叉搜索树中的众数
主要思路:
基于双指针中序遍历二叉搜索树,判断pre指针和cur指针指向的节点是否相同,如果相同,则当前节点的 count++,否则 count = 1;
当某个节点的出现频率与max_count相同时,将其放入结果数组;
更新众数时需要清空结果数组,并放入最大众数对应的节点;
#include <iostream>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
std::vector<int> findMode(TreeNode* root) {
dfs(root);
return res;
}
void dfs(TreeNode* cur){
if(cur == nullptr) return;
// 左
dfs(cur->left);
if(pre == nullptr || cur->val != pre->val){
count = 1;
}
else{
count++;
}
if(count == max_count) res.push_back(cur->val);
if(count > max_count){
max_count = count;
res.clear();
res.push_back(cur->val);
}
pre = cur; // 双指针
dfs(cur->right);
}
private:
int max_count = 0;
int count = 0;
std::vector<int> res;
TreeNode *pre = nullptr;
};
int main(int argc, char* argv[]){
// root = [1,null,2,2]
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(2);
Node1->right = Node2;
Node2->left = Node3;
Solution S1;
std::vector<int> res = S1.findMode(Node1);
for(int v : res) std::cout << v << " ";
std::cout << std::endl;
return 0;
}
21--二叉树的最近公共祖先
主要思路:
递归自底向上寻找,找到目标节点就返回;对于一个节点,若其左右子树均找到目标节点,则该节点即为最近公共祖先;
若只有一颗子树能找到目标节点,则该子树的返回结果就是最近公共祖先;
#include <iostream>
#include <string>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* res = dfs(root, p, q);
return res;
}
TreeNode* dfs(TreeNode* root, TreeNode* p, TreeNode* q){
if(root == nullptr) return nullptr;
if(root->val == p->val || root->val == q->val) return root;
TreeNode* left = dfs(root->left, p, q);
TreeNode* right = dfs(root->right, p, q);
if(left != nullptr && right != nullptr) return root;
else if(left != nullptr && right == nullptr) return left;
else return right;
}
};
int main(int argc, char* argv[]){
// root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
TreeNode* Node1 = new TreeNode(3);
TreeNode* Node2 = new TreeNode(5);
TreeNode* Node3 = new TreeNode(1);
TreeNode* Node4 = new TreeNode(6);
TreeNode* Node5 = new TreeNode(2);
TreeNode* Node6 = new TreeNode(0);
TreeNode* Node7 = new TreeNode(8);
TreeNode* Node8 = new TreeNode(7);
TreeNode* Node9 = new TreeNode(4);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Node3->left = Node6;
Node3->right = Node7;
Node5->left = Node8;
Node5->right = Node9;
Solution S1;
TreeNode *res = S1.lowestCommonAncestor(Node1, Node2, Node3);
if(res != nullptr) std::cout << res->val << std::endl;
else std::cout << "null" << std::endl;
return 0;
}
22--二叉搜索树的最近公共祖先
主要思路:
递归寻找,根据节点大小判断在左子树还是右子树寻找目标节点;
对于一个节点,假如其值在两个目标节点中间,则该节点为最近公共祖先;
#include <iostream>
#include <string>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* res = dfs(root, p, q);
return res;
}
TreeNode* dfs(TreeNode* root, TreeNode* p, TreeNode* q){
if(root == nullptr) return nullptr;
if(root->val > p->val && root->val > q->val){
return dfs(root->left, p, q);
}
else if(root->val < p->val && root->val < q->val){
return dfs(root->right, p, q);
}
else return root;
}
};
int main(int argc, char* argv[]){
// root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
TreeNode* Node1 = new TreeNode(6);
TreeNode* Node2 = new TreeNode(2);
TreeNode* Node3 = new TreeNode(8);
TreeNode* Node4 = new TreeNode(0);
TreeNode* Node5 = new TreeNode(4);
TreeNode* Node6 = new TreeNode(7);
TreeNode* Node7 = new TreeNode(9);
TreeNode* Node8 = new TreeNode(3);
TreeNode* Node9 = new TreeNode(5);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Node3->left = Node6;
Node3->right = Node7;
Node5->left = Node8;
Node5->right = Node9;
Solution S1;
TreeNode *res = S1.lowestCommonAncestor(Node1, Node2, Node3);
if(res != nullptr) std::cout << res->val << std::endl;
else std::cout << "null" << std::endl;
return 0;
}
23--二叉搜索树中的插入操作
主要思路:
任意一个节点的插入位置都能在叶子节点上找到,因此只需要递归遍历找到合适的叶子节点位置,将插入节点放到叶子节点位置即可;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
return dfs(root, val);
}
TreeNode* dfs(TreeNode* root, int val){
if(root == nullptr){ // 找到叶子节点位置了
TreeNode* target = new TreeNode(val);
return target;
}
if(root->val > val){
root->left = dfs(root->left, val);
}
else if(root->val < val){
root->right = dfs(root->right, val);
}
return root;
}
};
int main(int argc, char* argv[]){
TreeNode* Node1 = new TreeNode(4);
TreeNode* Node2 = new TreeNode(2);
TreeNode* Node3 = new TreeNode(7);
TreeNode* Node4 = new TreeNode(1);
TreeNode* Node5 = new TreeNode(3);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
int val = 5;
Solution S1;
TreeNode *res = S1.insertIntoBST(Node1, val);
// 层次遍历
std::queue<TreeNode *> q;
q.push(res);
while(!q.empty()){
TreeNode* tmp = q.front();
q.pop();
std::cout << tmp->val << " ";
if(tmp->left != nullptr){
q.push(tmp->left);
}
if(tmp->right != nullptr){
q.push(tmp->right);
}
}
std::cout << std::endl;
return 0;
}
24--删除二叉搜索树中的节点
主要思路:
删除节点有以下 5 种情况:
① 找不到删除的节点,返回 nullptr;
② 删除节点的左右孩子均为空(即为叶子节点),返回 nullptr;
③ 删除节点的左不空,右空,返回左孩子;
④ 删除节点的右不空,左空,返回右孩子;
⑤ 删除节点的左右均不空,记录删除节点的左孩子,然后递归删除节点的右孩子,找到最左边的叶子节点,将原先记录的删除节点的左孩子放到叶子结点的左孩子中;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
return dfs(root, key);
}
TreeNode* dfs(TreeNode* root, int key){
if(root == nullptr) return nullptr; // 删除节点不存在
if(root->val == key){ // 找到删除的叶子节点
if(root->left == nullptr && root->right == nullptr){
TreeNode *tmp = root;
delete(tmp);
return nullptr;
}
else if(root->left != nullptr && root->right == nullptr){
TreeNode *tmp = root;
TreeNode *left = root->left;
delete(tmp);
return left;
}
else if(root->left == nullptr && root->right != nullptr){
TreeNode *tmp = root;
TreeNode *right = root->right;
delete(tmp);
return right;
}
else{ // root->left != nullptr && root->right != nullptr
TreeNode* left = root->left; // 记录其左子树
TreeNode* right = root->right;
TreeNode* cur = root->right;
while(cur -> left != nullptr){ // 递归其右子树
cur = cur->left;
}
cur->left = left; // 将左子树作为右子树最左边的叶子节点的左孩子
delete(root);
return right; // 返回右子树
}
}
if(root->val > key) root->left = dfs(root->left, key);
else root->right = dfs(root->right, key);
return root;
}
};
int main(int argc, char* argv[]){
TreeNode* Node1 = new TreeNode(5);
TreeNode* Node2 = new TreeNode(3);
TreeNode* Node3 = new TreeNode(6);
TreeNode* Node4 = new TreeNode(2);
TreeNode* Node5 = new TreeNode(4);
TreeNode* Node6 = new TreeNode(7);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Node3->right = Node6;
int key = 3;
Solution S1;
TreeNode *res = S1.deleteNode(Node1, key);
// 层次遍历
std::queue<TreeNode *> q;
q.push(res);
while(!q.empty()){
TreeNode* tmp = q.front();
q.pop();
std::cout << tmp->val << " ";
if(tmp->left != nullptr){
q.push(tmp->left);
}
if(tmp->right != nullptr){
q.push(tmp->right);
}
}
std::cout << std::endl;
return 0;
}
25--修建二叉搜索树
主要思路:
对于小于左边界的节点,则其左子树所有节点都会小于左边界,因此可以舍弃;但仍需要递归判断其右子树;
对于大于右边界的节点,则其右子树所有节点都会大于右边界,因此可以舍弃;但仍需要递归判断其左子树;
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
return dfs(root, low, high);
}
TreeNode* dfs(TreeNode* root, int low, int high){
if(root == nullptr) return nullptr;
if(root->val < low){
return dfs(root->right, low, high);
}
if(root->val > high){
return dfs(root->left, low, high);
}
root->left = dfs(root->left, low, high);
root->right = dfs(root->right, low, high);
return root;
}
};
int main(int argc, char* argv[]){
// root = [1,0,2], low = 1, high = 2
TreeNode* Node1 = new TreeNode(1);
TreeNode* Node2 = new TreeNode(0);
TreeNode* Node3 = new TreeNode(2);
Node1->left = Node2;
Node1->right = Node3;
int low = 1, high = 2;
Solution S1;
TreeNode *res = S1.trimBST(Node1, low, high);
// 层次遍历
std::queue<TreeNode *> q;
q.push(res);
while(!q.empty()){
TreeNode* tmp = q.front();
q.pop();
std::cout << tmp->val << " ";
if(tmp->left != nullptr){
q.push(tmp->left);
}
if(tmp->right != nullptr){
q.push(tmp->right);
}
}
std::cout << std::endl;
return 0;
}
26--将有序数组转换为二叉搜索树
主要思路:
二分有序数组,递归构造左子树和右子树;
#include <iostream>
#include <queue>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* sortedArrayToBST(std::vector<int>& nums) {
TreeNode* res = dfs(nums, 0, nums.size() - 1);
return res;
}
TreeNode* dfs(std::vector<int>& nums, int left, int right){
if(left > right) {
return nullptr;
}
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = dfs(nums, left, mid - 1);
root->right = dfs(nums, mid + 1, right);
return root;
}
};
int main(int argc, char* argv[]){
// nums = [-10,-3,0,5,9]
std::vector<int> nums = {-10, -3, 0, 5, 9};
Solution S1;
TreeNode *res = S1.sortedArrayToBST(nums);
// 层次遍历二叉树
std::queue<TreeNode*> q;
q.push(res);
while(!q.empty()){
TreeNode* tmp = q.front();
q.pop();
std::cout << tmp->val << " ";
if(tmp->left != nullptr) q.push(tmp->left);
if(tmp->right != nullptr) q.push(tmp->right);
}
return 0;
}
27--把二叉搜索树转换为累加树
主要思路:
二叉搜索树按照 左→根→右 的顺序遍历是一个升序数组,则按照右 → 根 → 左的顺序遍历就是一个降序数组;
因此可以按照降序的顺序遍历,将当前节点的值更新为当前节点的值+前一个节点的值;文章来源:https://www.toymoban.com/news/detail-693367.html
用一个变量 pre 来记录上一个节点的值(类似于求二叉树众数的双指针),每遍历一个节点,更新 pre 的值;文章来源地址https://www.toymoban.com/news/detail-693367.html
#include <iostream>
#include <queue>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
dfs(root);
return root;
}
void dfs(TreeNode* cur){
if(cur == nullptr) return;
// 右
dfs(cur->right);
// 中
cur->val = pre + cur->val;
pre = cur->val; // 更新pre
// 左
dfs(cur->left);
}
private:
int pre = 0;
};
int main(int argc, char* argv[]){
// [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
TreeNode* Node1 = new TreeNode(4);
TreeNode* Node2 = new TreeNode(1);
TreeNode* Node3 = new TreeNode(6);
TreeNode* Node4 = new TreeNode(0);
TreeNode* Node5 = new TreeNode(2);
TreeNode* Node6 = new TreeNode(5);
TreeNode* Node7 = new TreeNode(7);
TreeNode* Node8 = new TreeNode(3);
TreeNode* Node9 = new TreeNode(8);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Node3->left = Node6;
Node3->right = Node7;
Node5->right = Node8;
Node7->right = Node9;
Solution S1;
TreeNode *res = S1.convertBST(Node1);
// 层次遍历二叉树
std::queue<TreeNode*> q;
q.push(res);
while(!q.empty()){
TreeNode* tmp = q.front();
q.pop();
std::cout << tmp->val << " ";
if(tmp->left != nullptr) q.push(tmp->left);
if(tmp->right != nullptr) q.push(tmp->right);
}
return 0;
}
到了这里,关于代码随想录笔记--二叉树篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!