# Binary Tree Path is target number

• Given a binary tree and a target number, return whether or not there exist a path that can create target number. All inputs are integers.
NOTE:: this is not path sums to target number
ex:
3
4 5
6 7 8 9

359 = return true
38 = return false
47 = return true
6 = return true

• @dinh.ho.14

This was my solution.

``````public static boolean treeContainsNumber(TreeNode root, int target) {
TreeNode startNode = findStart(root, target); // O(n) work to find node
if (startNode.val == target) {
return true;
}
// now that we have a potential starting point, travese down this point and see if we can create a path
return containsNumber(startNode, target, 0); // O(n) work to find the number containing the number
}

public static boolean containsNumber(TreeNode node, int target, int current) {
if (node == null) {
return false;
}

int newSum = (current * 10) + node.val;
int difference = target - newSum;
if (difference < 0) {
return false;
}

if (difference == 0) {
return true;
}

boolean foundNumber = containsNumber(node.left, target, newSum);
if (foundNumber == false) {
foundNumber = containsNumber(node.right, target, newSum);
}
return foundNumber;
}

public static TreeNode findStart(TreeNode node, int target) {
// find the first number of the target and see if we have a node that starts with this
int temp = target;
int num = 0;
while (temp > 0) {
num = temp % 10;
temp = temp / 10;
}
return findStartHelper(node, num);
}

public static TreeNode findStartHelper(TreeNode node, int value) {
if (node == null) {
return null;
}

if (node.val == value) {
return node;
}

TreeNode foundNode = findStartHelper(node.left, value);
if (foundNode == null) {
foundNode = findStartHelper(node.right, value);
}
return foundNode;
}``````

• This is my solution.

``````//binary tree is represent in a vector
bool hasPath(vector<int> v, int trg){
int N=v.size();
if(N==0)return false;
vector<int> v1;
v1.push_back(trg%10);
while(trg/10){
trg=trg/10;
v1.push_back(trg%10);
}
//extract each number of target
int N1=v1.size();
for(int i=0;i<N;++i){
if(v[i]==v1[N1-1]){
int pos=i;
int pos1=N1-1;
while(pos1!=0){
if(pos*2+1<N&&v[pos*2+1]==v1[pos1-1])pos=pos*2+1; // search left child
else if(pos*2+2<N&&v[pos*2+2]==v1[pos1-1])pos=pos*2+2; // search right child
else break;
pos1--;
}
if(pos1==0)return true;
}
}
return false;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.