Grokking the Coding Interview: The Original Course
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 -> 6root-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
· 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%