Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/99.html
You are given the root
of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
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]
. -231 <= Node.val <= 231 - 1
Follow up: A solution using O(n)
space is pretty straight-forward. Could you devise a constant O(1)
space solution?
Algorithm
Three pointers are needed, first
and second
respectively represent the first and second disordered nodes, and pre
points to the previous node of the current
node’s in-order traversal.
The traditional in-order traversal recursion is used here, but where the node value should be output, it is replaced by judging the size of pre and the current
node value. If pre is larger, if first is empty, first
point to the node pointed to by pre
, or else, set second
to the current
node.
In this way, the in-order traverses the entire tree, and if both first and second exist, then their node values can be exchanged. The space complexity of this algorithm is still O(n)
, where n
is the height of the tree.
Code
-
public class Recover_Binary_Search_Tree { public static void main(String[] args) { } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { TreeNode n1; TreeNode n2; TreeNode prev; // @note:@memorize: key is use prev! public void recoverTree(TreeNode root) { inOrderTraversal(root); // will record 2 swapped nodes swap(); // swap 2 nodes } private void inOrderTraversal(TreeNode root) { if (root == null) { return; } inOrderTraversal(root.left); // @note: 1,6,3,4,5,2 => NOT next to each other => n1=6-prev, but n2=2-root // @note: 1,2,4,3,5,6 => when next to each other, n2 needs to be root // bigger than next, then wrong if (prev != null && prev.val >= root.val) { if (n1 == null) { n1 = prev; n2 = root; // @note:@memorize: here is key, for case when in total two nodes } else { // n2 = prev; @note:@memorize: n1 and n2, n1=prev but n2=root n2 = root; } } prev = root; inOrderTraversal(root.right); } // @note: concern about n1 or n2 is null? by question definition, if swapped, then at least 2 nodes private void swap() { int tmp = n1.val; n1.val = n2.val; n2.val = tmp; } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private TreeNode prev; private TreeNode first; private TreeNode second; public void recoverTree(TreeNode root) { dfs(root); int t = first.val; first.val = second.val; second.val = t; } private void dfs(TreeNode root) { if (root == null) { return; } dfs(root.left); if (prev != null && prev.val > root.val) { if (first == null) { first = prev; } second = root; } prev = root; dfs(root.right); } }
-
// OJ: https://leetcode.com/problems/recover-binary-search-tree/ // Time: O(N) // Space: O(H) class Solution { TreeNode *a = NULL, *b = NULL; void update(TreeNode *x, TreeNode *y) { if (!a || x->val < a->val) a = x; if (!b || y->val > b->val) b = y; } void dfs(TreeNode *root, TreeNode *left = NULL, TreeNode *right = NULL) { if (!root) return; if (left && left->val > root->val) update(root, left); if (right && right->val < root->val) update(right, root); dfs(root->left, left, root); dfs(root->right, root, right); } public: void recoverTree(TreeNode* root) { dfs(root); swap(a->val, b->val); } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def recoverTree(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ def dfs(root): if root is None: return # inside a dfs(), 'nonlocal' is must if 'prev' being modified nonlocal prev, first, second dfs(root.left) if prev and prev.val > root.val: if first is None: first = prev second = root prev = root dfs(root.right) prev = first = second = None dfs(root) first.val, second.val = second.val, first.val ############ class Solution: def __init__(self): self.n1 = None self.n2 = None self.pre = None def findBadNode(self, root): if root is None: return self.findBadNode(root.left) if self.pre is not None: if root.val < self.pre.val: if self.n1 is None: self.n1 = self.pre self.n2 = root else: self.n2 = root self.pre = root self.findBadNode(root.right) def recoverTree(self, root): self.findBadNode(root) if self.n1 is not None and self.n2 is not None: self.n1.val, self.n2.val = self.n2.val, self.n1.val
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func recoverTree(root *TreeNode) { var prev, first, second *TreeNode var dfs func(*TreeNode) dfs = func(root *TreeNode) { if root == nil { return } dfs(root.Left) if prev != nil && prev.Val > root.Val { if first == nil { first = prev } second = root } prev = root dfs(root.Right) } dfs(root) first.Val, second.Val = second.Val, first.Val }
-
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {void} Do not return anything, modify root in-place instead. */ var recoverTree = function (root) { let prev = null; let first = null; let second = null; function dfs(root) { if (!root) { return; } dfs(root.left); if (prev && prev.val > root.val) { if (!first) { first = prev; } second = root; } prev = root; dfs(root.right); } dfs(root); const t = first.val; first.val = second.val; second.val = t; };
-
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private TreeNode prev, first, second; public void RecoverTree(TreeNode root) { dfs(root); int t = first.val; first.val = second.val; second.val = t; } private void dfs(TreeNode root) { if (root == null) { return; } dfs(root.left); if (prev != null && prev.val > root.val) { if (first == null) { first = prev; } second = root; } prev = root; dfs(root.right); } }