|
一。题目
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
示例1
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
二、思路
这道题难点，是找到那两个交换节点，把它交换过来就行了。这里我们二叉树搜索树的中序遍历(中序遍历遍历元素是递增的)
如下图所示，中序遍历顺序是 4,2,3,1，我们只要找到节点 4 和节点 1 交换顺序即可！
这里我们有个规律发现这两个节点：
第一个节点，是第一个按照中序遍历时候前一个节点大于后一个节点，我们选取前一个节点，这里指节点 4；
第二个节点，是在第一个节点找到之后，后面出现前一个节点大于后一个节点，我们选择后一个节点，这里指节点 1；
/**
* 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) {}
* };
*/
#define ElementType int
class Solution {
public:
TreeNode* firstNode = nullptr;
TreeNode* secondNode = nullptr;
TreeNode* preNode = new TreeNode(INT_MIN);
void recoverTree(TreeNode* root) {
inorderTraversal(root);
ElementType tmp = firstNode->val;
firstNode->val = secondNode->val;
secondNode->val = tmp;
}
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return ;
inorderTraversal(root->left);
if (firstNode == nullptr && preNode->val > root->val) firstNode = preNode;
if (firstNode != nullptr && preNode->val > root->val) secondNode = root;
preNode = root;
inorderTraversal(root->right);
}
};
// O(n) space complexity
class Solution {
public:
void recoverTree(TreeNode* root) {
vector<TreeNode*> list;
vector<int> vals;
inorder(root, list, vals);
sort(vals.begin(), vals.end());
for (int i = 0; i < list.size(); ++i) {
list[i]->val = vals[i];
}
}
void inorder(TreeNode* root, vector<TreeNode*>& list, vector<int>& vals) {
if (!root) return;
inorder(root->left, list, vals);
list.push_back(root);
vals.push_back(root->val);
inorder(root->right, list, vals);
}
};
三、进阶
使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
// Always O(n) space complexity
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *pre = NULL, *first = NULL, *second = NULL, *p = root;
stack<TreeNode*> st;
while (p || !st.empty()) {
while (p) {
st.push(p);
p = p->left;
}
p = st.top(); st.pop();
if (pre) {
if (pre->val > p->val) {
if (!first) first = pre;
second = p;
}
}
pre = p;
p = p->right;
}
swap(first->val, second->val);
}
};
参考：
https://www.cnblogs.com/grandyang/p/4298069.html
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/die-dai-fa-by-jason-2/
| 
转播
