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?

 

 

Subscribe to see which companies asked this question

解答：

这道题其实就是利用有错位时，中序遍历过程中会出现前后两个节点值的大小关系不符合BST性质的情况出现，这样只要把两个点都标记下来就好了……不过这里要注意1，2，3，4，5和1，3，2，4，5这样的错误只会在遍历中只会遇到一次错误情况，而1，2，3，4，5和3，2，1，4，5这样的错误在遍历中就会产生两次错误情况，所以在每一次遇到错误情况时就要标记两个点，如果有第二次遇到错误情况只要更新其中的一个标记就好了，当然要注意null节点……这个是用Java写的，用C写我不会啊TAT

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {      TreeNode tmp = null, mis_node_1 = null, mis_node_2;            void find_mistake(TreeNode root) {          if(root==null)               return;          find_mistake(root.left);         if(tmp != null&&root.val < tmp.val){              if(null == mis_node_1)                  mis_node_1 = tmp;              mis_node_2 = root;          }          tmp = root;          find_mistake(root.right);      }      public void recoverTree(TreeNode root) {            find_mistake(root);          if(null != mis_node_1){              int tmp_val = mis_node_1.val;              mis_node_1.val = mis_node_2.val;              mis_node_2.val = tmp_val;          }      }  }