有哪些做ppt的网站有哪些,网络技术学习网站,小学生免费编程课,网站如何备份数据目录
1--递归遍历
1-1--前序遍历
1-2--中序遍历
1-3--后序遍历
2--迭代遍历
2-1--前序遍历
2-2--后序遍历
2-3--中序遍历
3--二叉树的层序遍历
4--翻转二叉树
5--对称二叉树
6--二叉树最大深度
7--二叉树的最小深度
8--完全二叉树节点的数量
9--平衡二叉树
10-…目录
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 vectorstruct 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::vectorint preorderTraversal(TreeNode* root) {std::vectorint res;dfs(root, res);return res;}void dfs(TreeNode* root, std::vectorint 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::vectorint res S1.preorderTraversal(Node1);for(auto item : res) std::cout item ;std::cout std::endl;return 0;
}
1-2--中序遍历 中序遍历左→根→右 #include iostream
#include vectorstruct 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::vectorint inorderTraversal(TreeNode* root) {std::vectorint res;dfs(root, res);return res;}void dfs(TreeNode* root, std::vectorint 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::vectorint res S1.inorderTraversal(Node1);for(auto item : res) std::cout item ;std::cout std::endl;return 0;
}
1-3--后序遍历 后序遍历左→右→根 #include iostream
#include vectorstruct 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::vectorint postorderTraversal(TreeNode* root) {std::vectorint res;dfs(root, res);return res;}void dfs(TreeNode* root, std::vectorint 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::vectorint 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 stackstruct 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::vectorint preorderTraversal(TreeNode* root) {std::vectorint res;if(root nullptr) return res;std::stackTreeNode* 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::vectorint 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 algorithmstruct 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::vectorint postorderTraversal(TreeNode* root) {std::vectorint res;if(root nullptr) return res;std::stackTreeNode* 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::vectorint 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 algorithmstruct 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::vectorint inorderTraversal(TreeNode* root) {std::vectorint res;if(root nullptr) return res;std::stackTreeNode* 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::vectorint 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 queuestruct 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::vectorstd::vectorint levelOrder(TreeNode* root) {std::vectorstd::vectorint res;if(root nullptr) return res;std::queueTreeNode* q;q.push(root);while(!q.empty()){int nums q.size(); // 当前层的节点数std::vectorint 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::vectorstd::vectorint 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 queuestruct 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::queueTreeNode* 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 queuestruct 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 queuestruct 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 queuestruct 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 queuestruct 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 (2left_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 vectorstruct 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 stringstruct 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::vectorstd::string binaryTreePaths(TreeNode* root) {std::vectorstd::string res;if(root nullptr) return res;std::string path ;dfs(root, res, path);return res;}void dfs(TreeNode *root, std::vectorstd::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::vectorstd::string res S1.binaryTreePaths(Node1);for(auto path : res) std::cout path std::endl;return 0;
}
11--左叶子之和 主要思路 递归到叶子节点的上一层返回其左叶子之和 #include iostream
#include vector
#include stringstruct 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.hstruct 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, curheight1, max_height, res);dfs(root-right, curheight1, 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.hstruct 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 22TreeNode *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 queuestruct 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::vectorint inorder, std::vectorint postorder) {TreeNode *root dfs(inorder, postorder);return root;}TreeNode* dfs(std::vectorint inorder, std::vectorint 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::vectorint left_inorder(inorder.begin(), inorder.begin()idx); // 左子树的中序std::vectorint right_inorder(inorder.begin()idx1, inorder.end()); // 右子树的中序std::vectorint left_postorder(postorder.begin(), postorder.begin() left_inorder.size()); // 左子树的后序std::vectorint 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::vectorint inorder {9, 3, 15, 20, 7};std::vectorint postorder {9, 15, 7, 20, 3};Solution S1;TreeNode *root S1.buildTree(inorder, postorder);// 层次遍历std::queueTreeNode* 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.hstruct 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::vectorint nums) {TreeNode *root dfs(nums);return root;}TreeNode* dfs(std::vectorint 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::vectorint left_nums(nums.begin(), nums.begin() max_idx);root-left dfs(left_nums);}if(max_idx nums.size() - 1){std::vectorint 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::vectorint nums {3, 2, 1, 6, 0, 5};Solution S1;TreeNode *root S1.constructMaximumBinaryTree(nums);// 层次遍历std::queueTreeNode* 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.hstruct 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::queueTreeNode* 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 iostreamstruct 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 2TreeNode *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.hstruct 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 vectorstruct 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::vectorint 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::vectorint 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.hstruct 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 vectorstruct 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::vectorint 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::vectorint 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::vectorint res S1.findMode(Node1);for(int v : res) std::cout v ;std::cout std::endl;return 0;
}
21--二叉树的最近公共祖先 主要思路 递归自底向上寻找找到目标节点就返回对于一个节点若其左右子树均找到目标节点则该节点即为最近公共祖先 若只有一颗子树能找到目标节点则该子树的返回结果就是最近公共祖先 #include iostream
#include string
#include vectorstruct 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 1TreeNode* 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 vectorstruct 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 8TreeNode* 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 queuestruct 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::queueTreeNode * 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 queuestruct 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 ! nullptrTreeNode* 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::queueTreeNode * 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 queuestruct 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 2TreeNode* 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::queueTreeNode * 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 vectorstruct 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::vectorint nums) {TreeNode* res dfs(nums, 0, nums.size() - 1);return res;}TreeNode* dfs(std::vectorint 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::vectorint nums {-10, -3, 0, 5, 9};Solution S1;TreeNode *res S1.sortedArrayToBST(nums);// 层次遍历二叉树std::queueTreeNode* 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--把二叉搜索树转换为累加树 主要思路 二叉搜索树按照 左→根→右 的顺序遍历是一个升序数组则按照右 → 根 → 左的顺序遍历就是一个降序数组 因此可以按照降序的顺序遍历将当前节点的值更新为当前节点的值前一个节点的值 用一个变量 pre 来记录上一个节点的值类似于求二叉树众数的双指针每遍历一个节点更新 pre 的值 #include iostream
#include queue
#include vectorstruct 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::queueTreeNode* 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;
}
