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);
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容