Shulou(Shulou.com)06/01 Report--

Editor to share with you how to achieve the sum of LeetCode paths, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to understand it!

Topic description

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

Note: a leaf node is a node that does not have child nodes.

Example: given the following binary tree, and the target and sum = 22

5 /\ 4 8 /\ 11 13 4 /\ 7 2 1

Return true because there is a path 5-> 4-> 11-> 2 from the root node to the leaf node with a target and 22.

The idea of solving the problem

Tags: depth first traversal

Recursive termination condition:

Returns false when the current node is null

Returns true when the current node is the root node and the path sum is equal to the target sum

Recursive process: constantly judging left and right subtrees

Note: the problem of short circuit is involved here, that is, when a certain path is found and the condition is satisfied, the recursion should be ended, so the OR operation is used in the following solution, so there is no need to judge all the paths, but it ends if the conditions are satisfied. reduce time complexity

Code / * Definition for a binary tree node. * public class TreeNode {* int val; * TreeNode left; * TreeNode right; * TreeNode (int x) {val = x;} *} * / class Solution {public boolean hasPathSum (TreeNode root, int sum) {if (root = = null) return false; if (root.left = = null & root.right = = null & & sum = = root.val) return true Return hasPathSum (root.left, sum-root.val) | | hasPathSum (root.right, sum-root.val);}} above is all the content of the article "how to achieve path summation in LeetCode". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.