Problem:
Write a function that given a tree, returns true if at least 2 paths down the tree have the same sum. A path is a series of nodes from the root to the leaf. (题做出来还不给第二轮的某P家的电面题,不过解法确实不太好的感觉)
// ex1:
// 2
// / \
// 4 5
// /
// 1
// returns true // 2+4+1 = 2+5
// ex2:
// 3
// /
// 4
// / \
// 1 1
// returns true //3+4+1 = 3+4+1
// ex3:
// 1
// / \
// 3 4
// returns false // 1+3 != 1+4
Java Code:
public class PathSum {
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int value) {
this.val = value;
}
}
public static boolean pathSum(TreeNode root) {
if (root == null) {
return false;
}
if (root.left != null && root.right != null) {
boolean result = false;
int left = pathSumValue(root.left);
int right = pathSumValue(root.right);
result = pathSum(root.left) || pathSum(root.right) || (left == right);
return result;
}
if (root.left != null) {
return pathSum(root.left);
}
return pathSum(root.right);
}
public static int pathSumValue(TreeNode root) {
if (root.left == null && root.right == null) {
return root.val;
}
if (root.left == null) {
return pathSumValue(root.right) + root.val;
}
if (root.right == null) {
return pathSumValue(root.left) + root.val;
}
return pathSumValue(root.left) + pathSumValue(root.right);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(2);
root.left = new TreeNode(4);
root.right = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(1);
System.out.println(pathSum(root));
}
}
此评论已被作者删除。
回复删除