NC8题解 | #二叉树中和为某一值的路径(二)#
二叉树中和为某一值的路径(二)
http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
dfs递归解法
- 全局变量 ArrayList<ArrayList<>> ll保存所有路径
- 递归调用方法
- 传参：
- 上一级传递过来的root根节点
- 上一级传递过来的路径
- 上一级传递过来的数值
错误解法
错误解法：比较数值，小于期望值的就中断
错误原因：未考虑负数情况
public class Solution {
ArrayList<ArrayList<Integer>> ll = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
ArrayList<Integer> path = new ArrayList();
rec(root,path,expectNumber);
return ll;
}
public void rec(TreeNode root, ArrayList<Integer> path, int expectNumber){
if(root == null){
return;
}
ArrayList<Integer> newPath = new ArrayList(path);
if(expectNumber < root.val){
return;
}else if(expectNumber == root.val){
newPath.add(expectNumber);
if(root.left == null && root.right == null){
ll.add(newPath);
}
}else{
newPath.add(root.val);
int n = expectNumber - root.val;
rec(root.left,newPath,n);
rec(root.right,newPath,n);
}
}
}
正确解法
1、先判断是否叶子节点
2、判断是否等于预期值
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> ll = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
ArrayList<Integer> path = new ArrayList();
rec(root,path,expectNumber);
return ll;
}
public void rec(TreeNode root, ArrayList<Integer> path, int expectNumber){
if(root == null){
return;
}
ArrayList<Integer> newPath = new ArrayList(path);
newPath.add(root.val);
if(root.left != null){
rec(root.left, newPath, expectNumber - root.val);
}
if(root.right != null){
rec(root.right, newPath, expectNumber - root.val);
}
if(root.left == null && root.right == null){
if(root.val == expectNumber){
ll.add(newPath);
}
}
}
}
