首页 > 代码库 > leetcode[99] Recover Binary Search Tree
leetcode[99] Recover Binary Search Tree
题目：二叉树中有两个节点对换了值，恢复他们。
思路：
因为中序遍历是有序的，如果中序遍历后的数组出现乱序，说明就是交换的。从前往后，第一次乱序的第一个，后最后一次乱序的后一个，然后把这两个值对换就好了。
想了个非常挫的办法。
先中序遍历Binary Tree Inorder Traversal，然后在数组中找到两个值，然后再中序遍历找到那两个值，交换一下。虽然AC了，但不忍直视啊。
/** * 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 inorder(TreeNode *root, vector<int> &perm) // 中序遍历得到数组 { if (root == NULL) return ; stack<TreeNode *> sta; sta.push(root); TreeNode *p = root -> left, *cen; while(!sta.empty()) { if (p) { sta.push(p); p = p -> left; } else { cen = sta.top(); sta.pop(); perm.push_back(cen -> val); if (cen -> right) { sta.push(cen -> right); p = cen -> right -> left; } } } } void inorderC(TreeNode *root,int val1, int val2) // 中序遍历将对应值修改 { if (root == NULL) return ; stack<TreeNode *> sta; sta.push(root); TreeNode *p = root -> left, *cen; while(!sta.empty()) { if (p) { sta.push(p); p = p -> left; } else { cen = sta.top(); sta.pop(); if(cen -> val == val1) cen -> val = val2; else if(cen -> val == val2) cen -> val = val1; if (cen -> right) { sta.push(cen -> right); p = cen -> right -> left; } } } } void recoverTree(TreeNode *root) { if (!root) return ; vector<int> perm; inorder(root, perm); int val1, val2; bool flag = true; for (int i = 0; i < perm.size(); ++i) { if (flag && i + 1 < perm.size() && perm[i] > perm[i+1]) // 第一次比后一个大的数 { val1 = perm[i]; flag = false; } if (i - 1 >= 0 && perm[i] < perm[i-1]) // 最后一个比前面小的数 val2 = perm[i]; } inorderC(root, val1, val2); }};
然后就想到改进，在一次中序遍历中就记录两个节点，然后交换值。
leetcode[99] Recover Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。