Leetcode skimming: binary tree 16 (path sum)

112. The sum of the paths

Force button topic link

Given a binary tree and a target and , Determine whether there is a path from root node to leaf node in the tree , The sum of the values of all nodes in this path is equal to the target and .

explain : A leaf node is a node that has no children .

Example :
Given the following binary tree , And goals and sum = 22,

return true, Because there are goals and for 22 The path from the root node to the leaf node 5->4->11->2.

Recursive traversal , If there are only left trees , Then only the left subtree is calculated , If only the right subtree , Then only the right subtree is calculated , If you encounter an empty node, start comparing , Put the recursive result or operation that will do .

package com.programmercarl.tree;

import com.programmercarl.util.GenerateTreeNode;

import java.util.Stack;

/** * @ClassName HasPathSum * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 11:40 * @Version 1.0 * https://leetcode.cn/problems/path-sum/ * 112.  The sum of the paths  **/
public class HasPathSum {
    
    /** *  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 . * <p> * .. It's just to traverse every path and  * * @param root * @param targetSum * @return */
    public boolean hasPathSum(TreeNode root, int targetSum) {
    
        // Using recursion 
        if (root == null) {
    
            return false;
        }
        return traversal(root, 0, targetSum);
    }

    public boolean traversal(TreeNode root, int sum, int targetSum) {
    
        if (root == null) {
    
            return sum == targetSum;
        }
        // Calculate only to leaf nodes 
        sum += root.val;
        // Only the result of right subtree is calculated 
        if (root.left == null && root.right != null) {
    
            return traversal(root.right, sum, targetSum);
        }
        // Only calculate the result of the left subtree 
        if (root.left != null && root.right == null) {
    
            return traversal(root.left, sum, targetSum);
        }
        return traversal(root.left, sum, targetSum) || traversal(root.right, sum, targetSum);
    }

    public static void main(String[] args) {
    
        System.out.println(new HasPathSum().hasPathSum(GenerateTreeNode.generateTreeNode("[5,4,8,11,null,13,4,7,2,null,null,null,1]"), 22));
    }
}