1，递归方式解决
这题没说sum是正数还是负数，也没说树中节点的值有没有负数。我们要做的是从根节点到叶子节点遍历他所有的路径，返回他所有路径中和等于sum的节点，这里有两种实现方式，一种是减，一种是加。减就是从根节点开始，用sum不断的减去遍历到的每一个节点，一直到叶子节点，在减去叶子节点之前查看sum是否等于叶子节点，如果等于说明我们找到了一组，画个图看一下
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
dfs(root, sum, new ArrayList<>(), result);
return result;
}
public void dfs(TreeNode root, int sum, List<Integer> list,
List<ArrayList<Integer>> result) {
//如果节点为空直接返回
if (root == null)
return;
//因为list是引用传递，为了防止递归的时候分支污染，我们要在每个路径
//中都要新建一个subList
ArrayList<Integer> subList = new ArrayList<>(list);
//把当前节点值加入到subList中
subList.add(new Integer(root.val));
//如果到达叶子节点，就不能往下走了，直接return
if (root.left == null && root.right == null) {
//如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
//要把它放到result中
if (sum == root.val)
result.add(subList);
//到叶子节点之后直接返回，因为在往下就走不动了
return;
}
//如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
//下一步的时候，sum值要减去当前节点的值
dfs(root.left, sum - root.val, subList, result);
dfs(root.right, sum - root.val, subList, result);
}
看下运行结果
2，回溯，往下减
上面只是对二叉树的深度优先搜索（DFS），并没有使用回溯，之前讲递归的时候提到过为了防止分支污染我们还可以把使用过的值在返回的时候把它给remove掉，这就是大家常提的回溯算法，也可以看下之前讲的426，什么是递归，通过这篇文章，让你彻底搞懂递归 ，看下代码
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
dfs(root, sum, new ArrayList<>(), result);
return result;
}
public void dfs(TreeNode root, int sum, List<Integer> list,
List<ArrayList<Integer>> result) {
//如果节点为空直接返回
if (root == null)
return;
//把当前节点值加入到list中
list.add(new Integer(root.val));
//如果到达叶子节点，就不能往下走了，直接return
if (root.left == null && root.right == null) {
//如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
//要把它放到result中
if (sum == root.val)
result.add(new ArrayList(list));
//注意别忘了把最后加入的结点值给移除掉，因为下一步直接return了，
//不会再走最后一行的remove了，所以这里在rerurn之前提前把最后
//一个结点的值给remove掉。
list.remove(list.size() - 1);
//到叶子节点之后直接返回，因为在往下就走不动了
return;
}
//如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
//下一步的时候，sum值要减去当前节点的值
dfs(root.left, sum - root.val, list, result);
dfs(root.right, sum - root.val, list, result);
//我们要理解递归的本质，当递归往下传递的时候他最后还是会往回走，
//我们把这个值使用完之后还要把它给移除，这就是回溯
list.remove(list.size() - 1);
}
3，回溯，往下累加
上面是减的方式，我们再来看一个加的方式，其实他就是从根节点开始到叶子节点把这个路径上的所有节点都加起来，最后查看是否等于sum，画个图看一下
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
dfs(root, sum, 0, new ArrayList<>(), result);
return result;
}
public void dfs(TreeNode root, int sum, int toal, List<Integer> list,
List<ArrayList<Integer>> result) {
//如果节点为空直接返回
if (root == null)
return;
//把当前节点值加入到list中
list.add(new Integer(root.val));
//没往下走一步就要计算走过的路径和
toal += root.val;
//如果到达叶子节点，就不能往下走了，直接return
if (root.left == null && root.right == null) {
//如果到达叶子节点，并且sum等于toal，说明我们找到了一组，
//要把它放到result中
if (sum == toal)
result.add(new ArrayList(list));
//注意别忘了把最后加入的结点值给移除掉，因为下一步直接return了，
//不会再走最后一行的remove了，所以这里在rerurn之前提前把最后
//一个结点的值给remove掉。
list.remove(list.size() - 1);
//到叶子节点之后直接返回，因为在往下就走不动了
return;
}
//如果没到达叶子节点，就继续从他的左右两个子节点往下找
dfs(root.left, sum, toal, list, result);
dfs(root.right, sum, toal, list, result);
//我们要理解递归的本质，当递归往下传递的时候他最后还是会往回走，
//我们把这个值使用完之后还要把它给移除，这就是回溯
list.remove(list.size() - 1);
}
4，深度优先搜索非递归解决
树的dfs递归代码比较简单，我们来看一下树的dfs非递归的写法
public void treeDFS(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
System.out.println(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
可以参照上面的代码进行修改
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
//如果节点为空直接返回
if (root == null)
return res;
Stack<TreeNode> stackNode = new Stack<>();
Stack<ArrayList<Integer>> stackList = new Stack<>();
stackNode.add(root);
ArrayList<Integer> list = new ArrayList<>();
list.add(root.val);
stackList.add(list);
while (!stackNode.empty()) {
TreeNode node = stackNode.pop();
ArrayList<Integer> tempList = stackList.pop();
if (node.left == null && node.right == null && node.val == sum) {
//如果满足条件，就把路径存储到res中
res.add(tempList);
}
if (node.right != null) {
tempList.add(node.right.val);
stackList.add(new ArrayList<>(tempList));
node.right.val += node.val;
stackNode.push(node.right);
tempList.remove(tempList.size() - 1);
}
if (node.left != null) {
tempList.add(node.left.val);
stackList.add(new ArrayList<>(tempList));
node.left.val += node.val;
stackNode.push(node.left);
tempList.remove(tempList.size() - 1);
}
}
return res;
}
京公网安备 11010502036488号