最后更新
二刷
08-Jan-2017
利用线段树来更改，找到更改的NODE，然后更改那个brach上的所有max值。
首先确定recursion的终止条件
然后通过判断大小来找方向
找到NODE之后post order来进行更改。
public class Solution {
public void modify(SegmentTreeNode root, int index, int value) {
if (root == null) return;
if (index < root.start || index > root.end) return;
if (root.start == index && root.end == index) {
root.max = value;
} else {
int mid = root.start + (root.end - root.start) / 2;
if (index <= mid) {
modify(root.left, index, value);
} else {
modify(root.right, index, value);
}
root.max = Math.max(root.right.max, root.left.max);
}
}
}
看了下别人的做法，自己做的时候没想清楚。
一方面想判断走向来只遍历一边，一方面又添加了终止条件。
实际上如果添加终止条件，可以两边都走，走错的话会因为终止条件直接return。。但是毕竟多进了一个循环，所以时间慢一点点点点点
public class Solution {
public void modify(SegmentTreeNode root, int index, int value) {
if (root == null) return;
if (root.start > index || root.end < index) return;
if (root.start == index && root.end == index) {
root.max = value;
} else {
modify(root.left, index, value);
modify(root.right, index, value);
root.max = Math.max(root.left.max, root.right.max);
}
}
}