Binary tree - 112. Path sum

1 Title Description

Give you the root node of the binary tree root And an integer representing the sum of goals targetSum . Determine if there is Root node to leaf node The path of , The sum of the values of all nodes in this path is equal to the target and targetSum . If there is , return true ; otherwise , return false .

Leaf node A node without children .

Title Description source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/path-sum

2 Title Example

Example 3：

Input ：root = [], targetSum = 0
Output ：false
explain ： Because the tree is empty , Therefore, there is no path from root node to leaf node .

3 Topic tips

The number of nodes in the tree is in the range [0, 5000] Inside
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

4 Ideas

Notice that the requirement of this question is , Ask if there is from 「 The root node 」 To a certain 「 Leaf node 」 The sum of nodes on the path is equal to the target sum . The core idea is to traverse the tree once , When traversing, record the path and path from the root node to the current node , To prevent double counting .

Here's the thing to watch out for , A given root May is empty .

Method 1 ： Breadth first search
First of all, we can think of using breadth first search , Record the path and path from the root node to the current node , To prevent double counting .

So we use two queues , Store the nodes to be traversed separately , And the path and from the root node to these nodes .
Complexity analysis

• Time complexity :o(N), among N Is the number of nodes in the tree . Access once for each node .
• Spatial complexity :o(N), among N Is the number of nodes in the tree . The space complexity mainly depends on the overhead of the queue , The number of elements in the queue will not exceed the number of nodes in the tree .

Method 2 ： recursive
Look at the function that we are asked to complete , We can sum up its functions : Ask if there is a from the current node root The path to the leaf node , Satisfy its path and sum.
Assume that the sum of the values from the root node to the current node is val , We can turn this big problem into a small problem : Whether there is a path from the child node of the current node to the leaf , Satisfy its path and sum - va1 .
It is not difficult to find that this satisfies the nature of recursion , If the current node is a leaf node , So let's judge directly sum Is it equal to va1 that will do ( Because the path and have been determined , Is the value of the current node , We just need to judge whether the path and meet the conditions ). If the current node is not a leaf node , We just need to recursively ask whether its child nodes can meet the conditions .
Complexity analysis

• Time complexity :O(N), among N Is the number of nodes in the tree . Access once for each node .
• Spatial complexity :O(H), among H Is the height of the tree . The space complexity mainly depends on the overhead of stack space during recursion , In the worst case , The trees are in chains , The space complexity is o(N). On average, the height of the tree is positively correlated with the logarithm of the number of nodes , The space complexity is O(log N).

5 My answer

Method 1 ： Breadth first search

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

Method 2 ： recursive

class Solution {
    
    public boolean hasPathSum(TreeNode root, int sum) {
    
        if (root == null) {
    
            return false;
        }
        if (root.left == null && root.right == null) {
    
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}