【Java - L - 0099】h - 恢复二叉搜索树

10/18 07:10
阅读数 9

题目描述

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

实现

  1. 中序遍历
class Solution {
   
   
    // BST 中序有序
    public void recoverTree(TreeNode root) {
   
   
        List<TreeNode> list = new ArrayList<>();
        // 中序遍历
        inorder(root, list);
        // 找到相邻不等为错误节点
        int[] nums = swapNodes(list);
        // 交换两个无序节点
        recover(root, 2, nums[0], nums[1]);
    }

    public void inorder(TreeNode root, List<TreeNode> list) {
   
   
        if (root == null) return;
        inorder(root.left, list);
        list.add(root);
        inorder(root.right, list);
    }

    //[1,2,3,4,5,6,7]。如果我们交换两个不相邻的数字,例如 2 和 6,原序列变成了 
    //a=[1,6,3,4,5,2,7],那么显然序列中有两个位置不满足i<a(i+1),
    // 体现为 6>3,5>2(两个位置),如果2,3相邻交换则一个节点
    public int[] swapNodes(List<TreeNode> list) {
   
   
        int x = -1, y = -1;
        for (int i = 0; i < list.size() - 1; ++i) {
   
   
            if (list.get(i + 1).val < list.get(i).val) {
   
   
                y = list.get(i + 1).val;
                if (x == -1) {
   
   
                    x = list.get(i).val;
                } else {
   
   
                    break;
                }
            }
        }
        return new int[]{
   
   x, y};
    }

    public void recover(TreeNode root, int count, int x, int y) {
   
   
        if (root != null) {
   
   
            if (root.val == x || root.val == y) {
   
   
                root.val = root.val == x ? y : x;
                if (--count == 0) {
   
   
                    return;
                }
            }
            recover(root.right, count, x, y);
            recover(root.left, count, x, y);
        }
    }
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部