最后更新
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;
}
}