本文共 2217 字，大约阅读时间需要 7 分钟。

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?

解题思路:

解法一: 空间复杂度为O(n),先序遍历BST,用线性表存储然后重新排序，再重新给BST赋值。 解法二:

转自

递归中序遍历二叉树，设置一个pre指针，记录当前节点中序遍历时的前节点，如果当前节点大于pre节点的值，说明需要调整次序。

有一个技巧是如果遍历整个序列过程中只出现了一次次序错误，说明就是这两个相邻节点需要被交换。如果出现了两次次序错误，那就需要交换这两个节点。解法跟原文有些不一样，原文的时间为6ms，下面解法为4ms。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {
       List
   
     res;    int counter;    public void recoverTree(TreeNode root) {        res = getValue(root);        counter = 0;        Collections.sort(res);        setValue(root);    }    public List
    
      getValue(TreeNode root){        List
     
       res = new ArrayList
      
       ();        if(root != null){            res.addAll(getValue(root.left));            res.add(root.val);            res.addAll(getValue(root.right));        }        return res;    }    public void setValue(TreeNode root){        if(root != null){            setValue(root.left);            root.val = res.get(counter++);            setValue(root.right);        }    }}
      
     
    
   

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {
       TreeNode mistake1,mistake2;    TreeNode prev = null;    public void recoverTree(TreeNode root) {        int temp;        if(root != null){            findMistake(root);            temp = mistake1.val;            mistake1.val = mistake2.val;            mistake2.val = temp;        }    }    public void findMistake(TreeNode root){        if(root != null){           findMistake(root.left);           if(prev != null && prev.val > root.val){               if(mistake1 == null){                   mistake1 = prev;                   mistake2 = root;               }               else                   mistake2 = root;           }           prev = root;           findMistake(root.right);       }    }}

转载地址：http://ttivi.baihongyu.com/