首页 > 代码库 > LeetCode--Recover Binary Search Tree
LeetCode--Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
confused what "{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void recoverTree(TreeNode *root) { if(root == NULL) return; vector<TreeNode*> res; pre_search(root,res); if(res.size() == 1) return; bool flag = false; vector<int> temp; for(int i=1; i<res.size(); i++) { if(res[i]->val <= res[i-1]->val) { if(flag == false) { temp.push_back(i-1); flag = true; } else { temp.push_back(i); flag = false; } } } int n = temp.size(); if(n == 1) { int pre = temp[0]; int t = res[pre]->val; res[pre]->val = res[pre+1]->val; res[pre+1]->val = t; } else { int pre = temp[0]; int end = temp[1]; int t = res[pre]->val; res[pre]->val = res[end]->val; res[end]->val = t; } return ; } void pre_search(TreeNode* root, vector<TreeNode*>& res) { if(root == NULL) return; pre_search(root->left,res); res.push_back(root); pre_search(root->right,res); } };
LeetCode--Recover Binary Search Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。