首页 > 代码库 > 【leetcode】Recover Binary Search Tree
【leetcode】Recover Binary Search Tree
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?
中序遍历解法O(n)space
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 void recoverTree(TreeNode *root) {13 vector<TreeNode *> nodes;14 dfs(root,nodes);15 int index1=-1;16 int index2=-1;17 for(int i=1;i<nodes.size();i++)18 {19 if(nodes[i]->val<nodes[i-1]->val)20 {21 if(index1==-1) index1=i-1;22 index2=i;23 }24 }25 26 int tmp=nodes[index1]->val;27 nodes[index1]->val=nodes[index2]->val;28 nodes[index2]->val=tmp;29 return;30 31 } 32 33 void dfs(TreeNode *root,vector<TreeNode *> &nodes)34 {35 if(root==NULL) return;36 dfs(root->left,nodes);37 nodes.push_back(root);38 dfs(root->right,nodes);39 }40 };
直接在中序遍历中进行判断，需要记录遍历中的前一个元素
如果前一个元素比当前元素大，则说明存在错误
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 void recoverTree(TreeNode *root) {13 14 TreeNode *firstError=NULL;15 TreeNode *secondError=NULL;16 TreeNode *pre=NULL;17 18 19 dfs(root,pre,firstError,secondError);20 21 int tmp=firstError->val;22 firstError->val=secondError->val;23 secondError->val=tmp;24 }25 26 void dfs(TreeNode *root,TreeNode *&pre,TreeNode *&firstError,TreeNode *&secondError)27 {28 if(root==NULL) return;29 30 dfs(root->left,pre,firstError,secondError);31 32 if(pre!=NULL&&pre->val>root->val)33 {34 if(firstError==NULL) firstError=pre;35 secondError=root;36 }37 pre=root;38 39 dfs(root->right,pre,firstError,secondError);40 }41 };
【leetcode】Recover Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。