LeetCode 116 | Path Sum II | Solution Explained (White + Algorithm in Java)
Вставка
- Опубліковано 11 жов 2024
- Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
Running Time: O(N^2)
Space Complexity: O(N)
Always be pluggin:
Slack Channel: join.slack.com...
Github: github.com/xav...
Facebook: / xavier.hollingsworth.3
Instagram: / xavierelon
LinkedIn: / xavier-hollingsworth-5...
Twitter: / elon_xavier
Great solution! An optimization to this solution is to keep reusing the same path instance across the traversals through backtracking
class Solution {
public List pathSum(TreeNode root, int sum) {
List paths = new ArrayList();
List path = new ArrayList();
preorder(root, sum, path, paths);
return paths;
}
private void preorder(TreeNode node, int sum, List path, List paths) {
if (node == null)
return;
sum -= node.val;
path.add(node.val);
if (node.left == null && node.right == null && sum == 0) {
paths.add(new ArrayList(path));
}
preorder(node.left, sum, path, paths);
preorder(node.right, sum , path, paths);
path.remove(path.size() - 1);
}
}
Hello I want to join the slack channel but the link isn't working. Help :(
Thank you I will update the description:
join.slack.com/t/xavierelonleetcode/shared_invite/zt-kgx31p2o-CU3DK4X2ndCY1CCY8k4fTQ