Google Interview Question
SDE1sCountry: United States
map<long, int> search(TreeNode *root){
if (root == NULL){
return map<long,int>();
}
if (root->left == NULL && root->right == NULL){
map<long, int> mp;
mp[root->val] = 1;
return mp;
}
map<long, int> l = search(root->left);
map<long, int> r = search(root->right);
map<long, int> ret;
if (l.size() != 0){
for (auto it = l.begin(); it != l.end(); ++it){
ret[it->first + root->val] += it->second;
}
}
if (r.size() != 0){
for (auto it = r.begin(); it != r.end(); ++it){
ret[it->first + root->val] += it->second;
}
}
return ret;
}
int pathSum(TreeNode *root, int target){
map<long, int> mp = search(root);
return mp[target];
}
import java.util.ArrayList;
- zvnemsadze December 15, 2017import java.util.List;
/**
* Created by zviad on 12/15/17.
*/
public class TreeNodes {
private static class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int val) {
this.val = val;
}
@Override
public String toString() {
return "TreeNode{" +
"val=" + val +
", parent=" + parent +
'}';
}
}
int pathSum(TreeNode root,int sum){
List<TreeNode> leafNode=new ArrayList<>();
findeLeafs(leafNode,root);
final int result[]={0};
leafNode.forEach(item->{
if(checkPathSum(item,sum)) {
result[0]++;
}
});
return result[0];
}
private Boolean checkPathSum(TreeNode treeNode ,int checksum){
if((checksum-treeNode.val)==0){
return true;
}else if(treeNode.parent==null){
return false;
}else{
return checkPathSum(treeNode.parent,checksum-treeNode.val);
}
}
private void findeLeafs(List<TreeNode> leafNodes,TreeNode root){
if(root.left==null && root.right==null){
leafNodes.add(root);
return;
}else{
if(root.left!=null){
root.left.parent=root;
findeLeafs(leafNodes,root.left);
}
if(root.right!=null){
root.right.parent=root;
findeLeafs(leafNodes,root.right);
}
}
}
public static void main(String argv[]){
TreeNodes treeNodes=new TreeNodes();
TreeNode treenode=new TreeNode(8);
treenode.left=new TreeNode(3);
treenode.right=new TreeNode(2);
treenode.left.left=new TreeNode(26);
treenode.left.right=new TreeNode(23);
treenode.right.left=new TreeNode(1);
treenode.right.left.left=new TreeNode(12);
System.out.println(treeNodes.pathSum(treenode,26));
}
}