99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

代码语言：javascript复制

class Solution {
       TreeNode pre=new TreeNode(Integer.MIN_VALUE);
         TreeNode first=null;
         TreeNode second=null;
    public void recoverTree(TreeNode root) {
        /**
        中序遍历正确
        123456
        中序遍历有节点交换的
        143256-> 4>3  3>2  我们想要交换4和2  也就是第一个>关系里面的第一个数, 第二个>关系的第二个数  节点不变,交换值即可
         */
      
         helper(root);
         //交换两个节点
         int temp=first.val;
         first.val=second.val;
         second.val=temp;
    }

    public void helper(TreeNode node){
        if(node==null)return ;
         helper(node.left);
        if(first==null&&pre.val>node.val) first=pre;
        if(first!=null&&pre.val>node.val) second=node;
        pre=node;
        helper(node.right);
    }
}

root 搜索

0 人点赞