线段树的构造

http://www.lintcode.com/zh-cn/problem/segment-tree-build/

注意点：

根节点用root表示
把start == end的判断和后面代码合并，可以少一次return
递归的两种条件：逐层简化；最简单的情况下有返回值（终止条件）。所以在判断递归是否成立时，先考虑这两个条件是否已经满足。

1  public SegmentTreeNode build(int start, int end) {
2      if(start == end) return new SegmentTreeNode(start, end);
3      if(start > end) return null;
4      SegmentTreeNode st = new SegmentTreeNode(start, end);
5      int left = start, right = (start + end) / 2;
6      st.left = build(left, right);
7      st.right = build(right + 1, end);
8      return st; 
9  }

View Code

 1 public SegmentTreeNode build(int start, int end) {
 2         // write your code here
 3         if (start > end) {
 4             return null;
 5         }
 6         SegmentTreeNode root = new SegmentTreeNode(start, end);
 7         if(start != end) {
 8            int mid = (start + end) / 2;
 9            root.left = build(start, mid);
10            root.right = build(mid + 1, end);
11         }
12         return root;
13     }

better