duo.xu.1@stonybrook.edu
BAN USERpublic class Solution {
public static int multiply(int a, int b) {
if (a == 0 || b == 0) {
return 0;
}
if (b == 1) {
return a;
}
boolean positiveFlag = true;
if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
positiveFlag = false;
}
a = Math.abs(a);
b = Math.abs(b);
if (a < b) {
a ^= b;
b ^= a;
a ^= b;
}
int ret1 = multiply(a, b/2);
int ret2 = multiply(a, b%2);
if (positiveFlag == false) {
return -(ret1+ret1+ret2)
}
else {
return ret1+ret1+ret2;
}
}
}
class TreeNode {
int val;
TreeNode leftchild;
TreeNode rightchild;
}
public class Solution {
public static TreeNode findCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
if (root == null || a == null || b == null) {
return null;
}
TreeNode ret = null;
traverse(root, a, b, ret);
return ret;
}
public static int traverse(TreeNode root, TreeNode a, TreeNode b, TreeNode ret) {
if (root == null) {
return 0;
}
if (root == a || root == b) {
return 1;
}
int value = traverse(root.leftchild, a, b, ret)+traverse(root.rightchild, a, b, ret);
if (value == 2) {
ret = root;
return 3;
}
else {
return value;
}
}
}
class TreeNode {
int val;
TreeNode leftchild;
TreeNode rightchild;
public TreeNode(int val) {
this.val = val;
leftchild = null;
rightchild = null;
}
}
public class Solution {
public static ArrayList<Integer> search(TreeNode root, int max, int min) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (root == null || max < min) {
return ret;
}
traverse(root, max, min, ret);
// binarySearch(root, max, min, ret);
return ret;
}
private static void traverse(TreeNode root, int max, int min, ArrayList<Integer> ret) {
if (root == null) return;
traverse(root.leftchild, max, min, ret);
if (root.val>=min && root.val<=max) {
ret.add(root.val);
}
traverse(root.rightchild, max, min, ret);
}
private static void binarySearch(TreeNode root, int max, int min, ArrayList<Integer> ret) {
if (root == null) return;
if (root.val < min) binarySearch(root.rightchild, max, min, ret);
else if (root.val > max) binarySearch(root.leftchild, max, min, ret);
else {
ret.add(root.val);
binarySearch(root.rightchild, max, min, ret);
binarySearch(root.leftchild, max, min, ret);
}
}
}
- duo.xu.1@stonybrook.edu February 25, 2013