Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * 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 {
- public void recoverTree(TreeNode root) {
- int[] outOfPlace = findOutOfPlace(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
- System.out.println(Arrays.toString(outOfPlace));
- TreeNode badRoot = find(root, outOfPlace[1]);
- int another = replace(badRoot, outOfPlace[0]);
- replace(badRoot, another);
- }
- private int[] findOutOfPlace(TreeNode node, int min, int max) {
- if (node == null) return null;
- if (node.val < min) return new int [] { node.val, min };
- if (node.val > max) return new int [] { node.val, max };
- int[] lResult = findOutOfPlace(node.left, min, node.val);
- if (lResult != null) return lResult;
- return findOutOfPlace(node.right, node.val, max);
- }
- private TreeNode find(TreeNode node, int val) {
- if (node == null) return null;
- if (node.val == val) return node;
- return find(val < node.val ? node.left: node.right, val);
- }
- private Integer replace(TreeNode node, int val) {
- if (node == null) return null;
- TreeNode next = val < node.val ? node.left: node.right;
- if (next == null) {
- int oldVal = node.val;
- node.val = val;
- return oldVal;
- }
- return replace(next, val);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement