Binary Tree Path is target number


  • 0
    D

    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


  • 0
    D

    @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;
    }

  • 0
    H

    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;
    }
    

Log in to reply
 

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