热门搜索 :
考研考公
您的当前位置:首页正文

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);
    }
Top