转载

[LeetCode] 99. Recover Binary Search Tree 恢复二叉搜索树 leetcode java

题目:

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

<strong>输入:</strong> [1,3,null,null,2]

   1
  /
 3
  /
   2

<strong>输出:</strong> [3,1,null,null,2]

   3
  /
 1
  /
   2

示例 2:

<strong>输入:</strong> [3,1,4,null,null,2]

  3
 / /
1   4
   /
  2

<strong>输出:</strong> [2,1,4,null,null,3]

  2
 / /
1   4
   /
  3

进阶:

使用 O( n ) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？

思路：

中序遍历二叉树，出现的节点的值会升序排序，如果有两个节点位置错了，那肯定会出现降序。设置一个pre节点指针，记录当前节点中序遍历时的前节点，如果当前节点小于pre节点的值，说明需要调整次序。如果在中序遍历时节点值出现了两次降序，第一个错误的节点为第一次降序时较大的节点，第二个错误节点为第二次降序时较小的节点。比如，原来的搜索二叉树在中序遍历的节点值依次为{1,2,3,4,5}，如果因为两个节点位置错了而出现{1,5,3,4,2}，第一次降序为5->3，所以第一个错误节点为5，第二次降序为4->2,所以第二个错误节点为2，将5和2换过来就可以恢复。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode pre;
    TreeNode first;
    TreeNode second;
      
    public void inorder(TreeNode root){  
        if(root == null)  
            return;  

        inorder(root.left);  
        if(pre == null){  
            pre = root;  //pre指针初始
        }else{  
            if(pre.val > root.val){  
                if(first == null){  
                    first = pre;//第一个逆序点
                }  
                second = root;  //不断寻找最后一个逆序点
            }  
            pre = root;  //pre指针每次后移一位
        }  
        inorder(root.right);  
    }  
      
    public void recoverTree(TreeNode root) {  
        pre = null;  
        first = null;  
        second = null;  
        inorder(root);  
        if(first!=null && second!=null){   
            int tmp = first.val;  
            first.val = second.val;  
            second.val = tmp;  
        }  
    }
}

原文 http://www.lisite.top/2018/07/14/leetcode-99-recover-binary-search-tree-恢复二叉搜索树-leetcode-java/558.html

正文到此结束