Recover Binary Search Tree (H)
題目
You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Example 1:
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:
Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
Constraints:
- The number of nodes in the tree is in the range
[2, 1000]. -2^31 <= Node.val <= 2^31 - 1
題意
給定一個BST，其中有兩個結點的值互換了導致這個BST不符合定義，要求找到這兩個結點并處理使滿足BST的性質，同時不能改變樹的結構，
思路
BST的性質：中序遍歷得到一個單調遞增的序列，
最簡單的O(N)空間的方法是先用中序遍歷得到序列，找到互換了的兩個結點，再將它們換回來，
O(1)空間方法：不能使用常規的遞回或堆疊的方法進行中序遍歷，改用Morris遍歷，中途找到互換的兩個結點，
代碼實作
Java
中序遍歷 - O(N)空間
class Solution {
public void recoverTree(TreeNode root) {
List<TreeNode> nodes = new ArrayList<>();
inorder(root, nodes);
TreeNode A = null, B = null;
for (int i = 1; i < nodes.size(); i++) {
if (nodes.get(i).val < nodes.get(i - 1).val) {
if (A == null) {
A = nodes.get(i - 1);
}
B = nodes.get(i);
}
}
int tmp = A.val;
A.val = B.val;
B.val = tmp;
}
private void inorder(TreeNode root, List<TreeNode> nodes) {
if (root == null) {
return;
}
inorder(root.left, nodes);
nodes.add(root);
inorder(root.right, nodes);
}
}
Morris遍歷 - O(1)空間
class Solution {
public void recoverTree(TreeNode root) {
TreeNode A = null, B = null;
TreeNode pre = null;
while (root != null) {
if (root.left != null) {
TreeNode node = root.left;
while (node.right != null && node.right != root) {
node = node.right;
}
if (node.right == null) {
node.right = root;
root = root.left;
continue;
} else {
node.right = null;
}
}
if (pre != null && root.val < pre.val) {
if (A == null) {
A = pre;
}
B = root;
}
pre = root;
root = root.right;
}
int tmp = A.val;
A.val = B.val;
B.val = tmp;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198460.html
標籤：其他
上一篇：Python自動化測驗踩坑記錄（企業中如何實施自動化測驗）
下一篇：1290. Convert Binary Number in a Linked List to Integer (E)