Grokking the Coding Interview: The Original Course
Vote

0% completed

​

Binary Tree Path Sum (easy)

Problem Statement

Given a root of the binary tree and an integer S, return true if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals S. Otherwise, return false.

Examples

Example 1:

  • Input: root = [1, 2, 3, 4, 5, 6, 7], S = 10
  • Expected Output: true
  • Justification: The tree has 1 -> 3 -> 6 root-to-leaf path having sum equal to 10.

Example 2:

  • Input: root = [12, 7, 1, 9, null, 10, 5], S = 23
  • Expected Output: true
  • Justification: The tree has `12 -> 1 -> 10

.....

.....

.....

Like the course? Get enrolled and start learning!
Lily jiang

Lily jiang

· 16 hours ago

I can came up with recursive way but the while loop is just very difficult for me to figure out. And when root is None, meaning a tree with 0 nodes, and sum is also 0, should we return False or True? def hasPath(self, root, sum): node = root if root is None: return sum ==0 sum -= node.val if not node.left and not node.right: if sum ==0: return True else: return False else: return self.hasPath(root.left, sum) or self.hasPath(root.right,sum)
L

lejafilip

· 2 years ago

static bool hasPath(TreeNode *root, int sum) {     if(!root)       return false;       std::stack<std::pair<TreeNode*, int>> nodes;     nodes.push({root, sum - root->val});     while(!nodes.empty())     {       auto node = nodes.top();       nodes.pop();       if(node.second == 0 && !node.first->left && !node.first->right)       {         return true;       }       if(node.first->left)         nodes.push({node.first->left, node.second - node.first->left->val});             if(node.first->right)         nodes.push({node.first->right, node.second - node.first->right->val});     }     return false;   }
N

Nafis Molla

· 4 years ago

how does the or work in the return statement? Are they both run simultaneously?

Show 3 replies

Reading Progress

0%


Vote for new content