Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”
📢 preface
| 🚀 Algorithm 🚀 |
- 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
- 🌲 tip: the programming languages used in this column are C# and Java
- 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
- 🌲 today is the force button algorithm continued to punch the card 32 days 🎈!
| 🚀 Algorithm 🚀 |
🌲 Example: Sum of paths
You are given the root node of the binary tree and an integer targetSum representing the targetSum. Determine if there is a path from the root node to the leaf node in the tree. The sum of all nodes in the path equals the target and targetSum.
A leaf node is a node that has no children.
Example 1:
Enter: root = [5.4.8.11,null,13.4.7.2,null,null,null,1], targetSum = 22Output:true
Copy the codeExample 2:
Enter: root = [1.2.3], targetSum = 5Output:false
Copy the codeThe sample3: Enter: root = [1.2], targetSum = 0Output:false
Copy the codeTip:
- The number of nodes in the tree is in the range [0, 5000]
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
🌻C# method: recursion
Looking at the function we are asked to complete, we can generalize its function: ask if there is a path from the current node root to the leaf node whose path sum is sum.
Given that the sum of the values from the root node to the current node is val, we can turn the big question into a smaller one: is there a path from the children of the current node to the leaf whose sum is sum-val?
If the current node is a leaf node, then we can directly determine whether sum is equal to val (since the path sum has already been determined, which is the value of the current node, we only need to determine whether the path sum satisfies the condition). If the current node is not a leaf node, we simply recursively ask its children if they meet the criteria.
Thinking analytical
Code:
public class Solution {
public bool HasPathSum(TreeNode root, int sum) {
/ / export
if (root == null)
{
return false;
}
if (root.left == null && root.right == null)
{
return root.val == sum;
}
returnHasPathSum(root.left, sum - root.val) || HasPathSum(root.right, sum - root.val); }}Copy the codeThe execution result
By time complexity: O(n), where n is the number of nodes in the tree. Space complexity: O(H), where H is the height of the treeCopy the codeComplexity analysis
Time complexity: O(n^2) where n is the length of the array. Each number is accessed only once. Space complexity: O(n), where n is the length of the array. The spatial complexity does not consider the return value, so the spatial complexity depends primarily on the depth of the recursive stack, which is O(logn).Copy the code🌻Java Method 1: breadth-first search
First, we can think of using breadth-first search to record the path sum from the root node to the current node to prevent double computation.
So we use two queues that store the nodes to be traversed, and the paths and values from the root node to those nodes.
Code:
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
Queue<TreeNode> queNode = new LinkedList<TreeNode>();
Queue<Integer> queVal = new LinkedList<Integer>();
queNode.offer(root);
queVal.offer(root.val);
while(! queNode.isEmpty()) { TreeNode now = queNode.poll();int temp = queVal.poll();
if (now.left == null && now.right == null) {
if (temp == sum) {
return true;
}
continue;
}
if(now.left ! =null) {
queNode.offer(now.left);
queVal.offer(now.left.val + temp);
}
if(now.right ! =null) { queNode.offer(now.right); queVal.offer(now.right.val + temp); }}return false; }}Copy the codeThe execution result
By execution time:2Ms, beat out all Java commits10.29% user memory consumption:38.3MB, beat out all Java commits67.32% of the userCopy the codeComplexity analysis
Time complexity: O(n), where n is the number of nodes in the tree. Space complexity: O(n), where n is the number of nodes in the tree.Copy the code🌻Java method 2: Recursion
Thinking analytical
Looking at the function we are asked to complete, we can generalize its function: ask if there is a path from the current node root to the leaf node whose path sum is sum.
Given that the sum of the values from the root node to the current node is val, we can turn the big question into a smaller one: is there a path from the children of the current node to the leaf whose sum is sum-val?
If the current node is a leaf node, then we can directly determine whether sum is equal to val (since the path sum has already been determined, which is the value of the current node, we only need to determine whether the path sum satisfies the condition). If the current node is not a leaf node, we simply recursively ask its children if they meet the criteria.
Code:
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = 0, p2 = 0;
int[] sorted = new int[m + n];
int cur;
while (p1 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i ! = m + n; ++i) { nums1[i] = sorted[i]; }}}Copy the codeThe execution result
By execution time:0Ms, beat out all Java commits100.00% user memory consumption:38.5MB, beat out all Java commits18.28% of the userCopy the codeComplexity analysis
Time complexity: O(n), where n is the number of nodes in the tree. Space complexity: O(H), where H is the height of the treeCopy the code💬 summary
- Today is the thirty-second day of clocking!
- The article USES the
C#andJavaTwo programming languages to solve the problem - Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
- That’s the end of today’s algorithm sharing, see you tomorrow!
