【递归】【回溯】Leetcode 112. 路径总和 113. 路径总和 II

如果需要搜索整棵二叉树，那么递归函数就不要返回值
如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回

112. 路径总和

---------------🎈🎈题目链接🎈🎈-------------------

解法：递归 有递归就有回溯 记得return正确的返回上去

count初始等于targetsum，逐次减，如果到了叶子结点正好count为0，那么就返回true
终止条件：if(root.left = null && root.right = null && count=0){ return true; }

时间复杂度O(N)
空间复杂度O(N)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {// 终止条件if(root == null) return false;int count = targetSum-root.val;return help(root,count);}public boolean help(TreeNode root, int count){if(root.left==null && root.right==null && count==0){return true;}if(root.left==null && root.right==null && count!=0){return false;}// 左if(root.left != null){if(help(root.left, count-root.left.val)){return true;}}// 右if(root.right != null){if(help(root.right, count-root.right.val)){return true;}}return false;}}

113. 路径总和 II

---------------🎈🎈题目链接🎈🎈-------------------

解法 递归

时间复杂度O(N)
空间复杂度O(N)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<List<Integer>> finalresult = new ArrayList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<Integer> result = new ArrayList<>();if(root == null) return finalresult;result.add(root.val);helper(root,targetSum-root.val,result);return finalresult;}public void helper(TreeNode root, int count, List<Integer> result){if(root.left == null && root.right==null && count==0){finalresult.add(new ArrayList<>(result)); // 这里千万不能finalresult.add(result) 这就成了添加result的引用，每次都会变}// 左if(root.left != null){result.add(root.left.val);helper(root.left, count-root.left.val,result);result.remove(result.size()-1); // 回溯}// 右if(root.right != null){result.add(root.right.val);helper(root.right,count-root.right.val,result);result.remove(result.size()-1); // 回溯}}
}