做团购网站的心得,成品视频直播软件推荐哪个好一点ios,百度小说排行榜2019,抚州网站开发思路#xff1a;
二叉搜索树的中序遍历是递增序列#xff0c;可以在中序遍历中记录两个需要交换的节点#xff0c;直到遍历完毕之后#xff0c;对两个节点的值进行交换即可得到正确的二叉搜索树
比如中序序列为 1 2 3 7 5 6 4#xff08;7比5大记录7为x#xf…
思路
二叉搜索树的中序遍历是递增序列可以在中序遍历中记录两个需要交换的节点直到遍历完毕之后对两个节点的值进行交换即可得到正确的二叉搜索树
比如中序序列为 1 2 3 7 5 6 47比5大记录7为x6比4大记录4为y交换x与y /*** Definition for a binary tree node.* 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* x nullptr;TreeNode* y nullptr;TreeNode* pre nullptr;void recoverTree(TreeNode* root) {//进行中序遍历dfs(root);//如果交换节点都不为空则进行val交换得到结果if(x!nullptry!nullptr){int temp x-val;x-val y -val;y-val temp;}}//中序遍历void dfs(TreeNode* root) {//如果为空节点返回if(root nullptr) return;//遍历左子树dfs(root-left);//如果当前节点为第一个节点则pre 当前节点if(pre nullptr) pre root;//如果当前节点前面有节点else{//如果当前节点的值小于前一个节点的值if(pre-val root-val){//记录当前节点的值不停的更新y的节点y root;//如果另一个节点为空则记录前一个节点固定x节点if(x nullptr) x pre;}//每次遍历都需要更新pre节点即当前节点为前一个节点pre root;}//遍历右子树dfs(root-right);}
};
