2021-02-18 根据后序遍历数组重建二叉搜索树

题目地址

无

题目描述

已知一个二叉搜索树的后序遍历数组，根据这个数组重建整个树。

思路

1. 这个和已知二叉树的两种遍历来重建二叉树类似。
2. 2,4,3,7,9,8,5。这个后序遍历，最后一个5肯定是根节点，因为是二叉搜索树，（2，4，3）肯定是左树，（7，9，8）肯定是右树，然后进入左右树，例如（2，4，3）最后一个节点3是根，右分左右，递归创建即可。
   PS：题解中查找左右子树的分界点的时候可以使用二分查找，在部分有序的序列中使用二分查找。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/18
 */
public class RebuildSortedTree {
    public static void main(String[] args) {
        int[] arr = {2,4,3,7,9,8,5};
        NodeTree root = rebuild(arr);
        root.preOrder(root);
    }

    private static NodeTree rebuild(int[] arr) {
        NodeTree root = doRebuild(arr, 0, arr.length-1);
        return root;
    }

    private static NodeTree doRebuild(int[] arr, int left, int right) {
        if (arr.length < 1 || left > right) {
            return null;
        }
        if (left == right) {
            return new NodeTree(arr[left]);
        }
        NodeTree root = new NodeTree(arr[right]);

        // 找左右子树的分界，这个可以用二分查找优化
        int mid = right - 1;
        while (mid > 0) {
            if (arr[mid] < root.getValue()) {
                break;
            }
            mid--;
        }
        root.setLeft(doRebuild(arr, left, mid));
        root.setRight(doRebuild(arr, mid + 1, right - 1));

        return root;
    }
}