恢复二叉搜索树

2019-07-30 09:07:00
二叉树 - 算法 - java

**二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1:

示例 2:

题目来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/recover-binary-search-tree**

解答

先放我的代码:

/**
 *  力扣中关于二叉树的默认定义
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode one = null;  //逆序中大的值
    TreeNode two = null;  //逆序中小的值
    TreeNode pre = null;    //上一个节点
    int temp;
    public void recoverTree(TreeNode root) {
        order(root);    //中序遍历找出逆序的两个数
        temp = one.val;
        one.val = two.val;
        two.val = temp;
    }

    public void order(TreeNode root){
        if(root==null) return;
        if(root.left!=null){
            order(root.left);
        }
        if(pre!=null && pre.val > root.val){
            if(one==null){
                one=pre; 
                two=root;   
            }
            else{
                two=root;
            }
        }
        pre=root;
        if(root.right!=null){
            order(root.right);
        }
    }
}

又是一道二叉树问题,做了几道后发现二叉树问题一般都是可以用递归解决的,所以思路就很明确了,递归!! 通过之前对二叉树的了解我知道了二叉树的遍历有: 先序遍历,中序遍历,后序遍历,层次遍历。 而题目又说的很明确,二叉搜索树!!对于二叉搜索树,百度百科有很清晰的解释: 这样的话解法就很清晰了,中序遍历+递归。先递归到最小的一个节点,从这个节点开始判断,若这个节点前一个数大于当前节点就说明有冲突,这两个数就是我们要找的数了。然鹅梦想是美好的现实是残酷的,没这么简单,我的想法仅限于相邻的两个数之间的交换,不得已看了一下官方题解,发现两个数冲突叫做逆序,而这个逆序有两种可能性,一种是相邻之间的逆序,一种是相隔几个数的逆序,前者会产生一组逆序的数字,后者会产生两组逆序的数组,因此需要在逆序那里多加一次判断,第一次逆序时把one赋给pre,也就是较大的值,root赋给two;第二次逆序时把root再次赋给two。如此一来,可以确保one里面存的就是大的那个数,two存的是小数。退出递归后recoverTree方法仅仅是把one.val和two.val交换即可恢复二叉搜索树。



本文原创于HhhM的博客,转载请标明出处。



CopyRight © 2019-2020 HhhM
Power By Django & Bootstrap
已运行
粤ICP备19064649号