[leetcode]99. Recover Binary Search Tree@Java解题报告

https://leetcode.com/problems/recover-binary-search-tree/description/

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O( n ) space is pretty straight forward. Could you devise a constant space solution?

package go.jacob.day805; public class Demo2 { //firstElem第一个被交换的element，secondElem被交换的element TreeNode firstElem = null, secondElem = null; //把上一个节点初始化为最小值 TreeNode preElem = new TreeNode(Integer.MIN_VALUE); public void recoverTree(TreeNode root) { // 中序遍历 inOrderTraverse(root); int tmp = firstElem.val; firstElem.val = secondElem.val; secondElem.val = tmp; } private void inOrderTraverse(TreeNode root) { if (root == null) return; inOrderTraverse(root.left); // 1234567到1264537 if (firstElem == null && preElem.val >= root.val) { firstElem = preElem; } if (firstElem != null && preElem.val >= root.val) { secondElem = root; } preElem = root; inOrderTraverse(root.right); } private class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }