剑指 Offer 34. 二叉树中和为某一值的路径
剑指 Offer 34. 二叉树中和为某一值的路径
1.先写一种错误的写法,这是自己第一次写的写法
/**
* 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 List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
LinkedList<Integer> path = new LinkedList<>();
fun(root,target,path);
return ans;
}
public void fun(TreeNode root, int target,List<Integer> path){
if(root==null&&target==0){
ans.add(path);
return;
}
if(target<=0||root==null){
return;
}
path.add(root.val);
List<Integer> pathLeft = new LinkedList<>(path);
List<Integer> pathRight = new LinkedList<>(path);
fun(root.left,target-root.val,pathLeft);
fun(root.right,target-root.val,pathRight);
}
}
这里要注意,List
同时,这种写法也是不对的,最后结果有重复值。
因为当最后有满足条件的值是在为空的的时候判断的,所以左右节点为空都会产生值。
正确写法
/**
* 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 List<List<Integer>> pathSum(TreeNode root, int target) {
List<List<Integer>> ans = new ArrayList<>();
dfs(root, target, new ArrayList<>(), ans);
return ans;
}
private void dfs(TreeNode node, int target, List<Integer> path, List<List<Integer>> result) {
if (node == null)
return;
List<Integer> newPath = new ArrayList<>(path);
newPath.add(node.val);
if (node.left == null && node.right == null && target == node.val) {
result.add(newPath);
}
dfs(node.left, target - node.val, newPath, result);
dfs(node.right, target - node.val, newPath, result);
}
}