您好,欢迎来到二三四教育网。
搜索
您的当前位置:首页Tree:Recover Binary Search Tree

Tree:Recover Binary Search Tree

来源:二三四教育网

Two elements of a binary search tree (BST) are swapped by mistake.Recover the tree without changing its structure.

public void recoverTree(TreeNode root) {
        ArrayList<TreeNode> ary = new ArrayList<TreeNode>();
        infixOrder(root, ary);
        TreeNode errorNodeAry[] = new TreeNode[2];
        int index = -1;
        for (int i = 0; i < ary.size()-1; i++) {
            if (ary.get(i).val>ary.get(i+1).val) {
                errorNodeAry[0] = ary.get(i);
                index = i;
                break;
            } 
        }
        if (errorNodeAry[0]==null) {
            errorNodeAry[0] = ary.get(ary.size()-1);
            index = 0;
        }
        for (int i = index+2; i < ary.size(); i++) {
            if (ary.get(i).val<ary.get(i-1).val) {
                errorNodeAry[1] = ary.get(i);
                break;
            }
        }
        if (errorNodeAry[1]==null) {
            errorNodeAry[1] = ary.get(index+1);
        }
        int temp = errorNodeAry[0].val;
        errorNodeAry[0].val = errorNodeAry[1].val;
        errorNodeAry[1].val = temp;
    }
    
    private void infixOrder(TreeNode node,ArrayList<TreeNode>ary) {
        if (node == null) {
            return;
        }
        infixOrder(node.left, ary);
        ary.add(node);
        infixOrder(node.right, ary);
    }

本文如未解决您的问题请添加抖音号:51dongshi(抖音搜索懂视),直接咨询即可。

热门图文

Copyright © 2019-2025 how234.cn 版权所有 赣ICP备2023008801号-2

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务