Saturday, January 17, 2015

[Algorithm]Get Path with Max Sum in Binary Tree

Binary Tree Maximum Path Sum的变形,这次是要把得到path而不是单纯的sum,解法也是类似的,只不过递归的时候return path,当在一个节点的时候,先得到左子树和右子树中最大的path,算出左边和右边的和,然后根据左边右边和自己的和判断是否需要更新最大值。然后return左边还是右边的策略和maximum path sum是一样的。T(N) = 2T(N/2) + O(N),O(N)是每次要根据path来算出sum,根据master therom,时间复杂度为O(N log N),代码如下:
package kimi;
import java.util.ArrayList;
public class GetMaxPath {
private ArrayList<Integer> res = new ArrayList<Integer>();
private int sum = Integer.MIN_VALUE;
public ArrayList<Integer> getPath(TreeNode root){
getMaxPath(root);
return res;
}
private ArrayList<Integer> getMaxPath(TreeNode node){
if (node == null)
return new ArrayList<Integer>();
ArrayList<Integer> left = getMaxPath(node.left);
ArrayList<Integer> right = getMaxPath(node.right);
int leftSum = 0, rightSum = 0;
for (int i = 0; i < left.size(); i++)
leftSum += left.get(i);
for (int i = 0; i < right.size(); i++)
rightSum += right.get(i);
if (leftSum + node.val + rightSum > sum) {
res = new ArrayList<Integer>(left);
res.add(node.val);
for (int i = right.size() - 1; i >= 0; i--)
res.add(right.get(i));
sum = leftSum + node.val + rightSum;
}
if (leftSum + node.val <= 0 && rightSum + node.val <= 0)
return new ArrayList<Integer>();
if (leftSum >= rightSum) {
left.add(node.val);
return left;
} else {
right.add(node.val);
return right;
}
}
//for test use, serialize path
public String serialize(ArrayList<Integer> path) {
int size = path.size();
String res = "#";
for (int i = 0; i < size; i++) {
if (i == 0)
res += path.get(i);
else
res += "," + path.get(i);
}
res += "#";
return res;
}
public static void main(String[] args) {
test1();
test2();
test3();
}
//test cases
private static void test1() {
TreeNode root = new TreeNode(1);
GetMaxPath g = new GetMaxPath();
System.out.println(g.serialize(g.getPath(null)));
System.out.println(g.serialize(g.getPath(root)));
}
private static void test2() {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(4);
root.left.left = new TreeNode(7);
root.left.left.left = new TreeNode(10);
root.right.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right.right = new TreeNode(1);
root.right.left.left = new TreeNode(-2);
root.left.left.right = new TreeNode(-3);
root.left.left.right.right = new TreeNode(0);
GetMaxPath g = new GetMaxPath();
System.out.println(g.serialize(g.getPath(root)));
}
private static void test3() {
TreeNode root = new TreeNode(-3);
root.left = new TreeNode(7);
root.right = new TreeNode(-6);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(-2);
root.right.right = new TreeNode(5);
root.left.left.left = new TreeNode(12);
root.left.left.left.right = new TreeNode(0);
root.left.right.right = new TreeNode(10);
root.right.right.left = new TreeNode(-8);
root.right.right.right = new TreeNode(-9);
root.right.right.left.left = new TreeNode(17);
root.right.right.right.right= new TreeNode(-20);
GetMaxPath g = new GetMaxPath();
System.out.println(g.serialize(g.getPath(root)));
}
}

No comments:

Post a Comment