2021-10-24（JZ34 二叉树中和为某一值的路径）

本文主要是介绍2021-10-24（JZ34 二叉树中和为某一值的路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

糟糕的复杂度，丑陋的写法

import java.util.ArrayList;
/**
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {ArrayList<ArrayList<Integer>> answer=new ArrayList<>();ArrayList<Integer> tempAnswer=new ArrayList<>();public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {if(root==null){return answer;}tempAnswer.add(root.val);dfs(root,expectNumber);return answer;}public void dfs(TreeNode root,int expectNumber){if(root.left==null&&root.right==null){int sum=0;for(int i=0;i<tempAnswer.size();++i){sum+=tempAnswer.get(i);}if(sum==expectNumber){answer.add(new ArrayList<>(tempAnswer));}return;}if(root.left!=null){tempAnswer.add(root.left.val);dfs(root.left,expectNumber);tempAnswer.remove(tempAnswer.size()-1);}if(root.right!=null){tempAnswer.add(root.right.val);dfs(root.right,expectNumber);tempAnswer.remove(tempAnswer.size()-1);}        }
}

修改之后，格式稍微好看点了，但判断小于0的剪枝是错的。因为有负数的存在。

import java.util.ArrayList;
/**
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {ArrayList<ArrayList<Integer>> answer=new ArrayList<>();ArrayList<Integer> tempAnswer=new ArrayList<>();public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {dfs(root,expectNumber);return answer;}public void dfs(TreeNode root,int remain){if(root==null){return;}tempAnswer.add(root.val);remain-=root.val;if(remain<0){tempAnswer.remove(tempAnswer.size()-1);return;}if(remain==0&&root.left==null&&root.right==null){answer.add(new ArrayList<>(tempAnswer));}dfs(root.left,remain);dfs(root.right,remain);tempAnswer.remove(tempAnswer.size()-1);}
}