最后更新

08-Jan-2017

开始介绍线段树的主要作用了，可以快速在区间查找极值，我猜是这样的。。。。。

一个NODE的最大值取决于它左边和右边最大值里大 按个，所以，所以什么？对了，我们该用post-order traversal来构建。

public class Solution {

    public SegmentTreeNode build(int[] A) {

        // write your code here

        if (A.length == 0) return null;

        return buildTree(A, 0, A.length - 1);

    }

    public SegmentTreeNode buildTree(int[] A, int left, int right) {

        if (left > right) return null;

        if (left == right) return new SegmentTreeNode(left, right, A[left]);

        int mid = left + (right - left) / 2;

        SegmentTreeNode leftChild = buildTree(A, left, mid);

        SegmentTreeNode rightChild = buildTree(A, mid + 1, right);

        SegmentTreeNode tempRoot = new SegmentTreeNode(left, right, Math.max(leftChild.max, rightChild.max));

        tempRoot.left = leftChild;

        tempRoot.right = rightChild;

        return tempRoot;

    }

}