您好,欢迎来到伴沃教育。
搜索
您的当前位置:首页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);
    }

Copyright © 2019- bangwoyixia.com 版权所有 湘ICP备2023022004号-2

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

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