二叉树根节点到叶子节点和为指定值的路径
package com.wy.tree;
import com.wy.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 1.递归,2.回溯,往下减,3.深度优先搜索非递归
*/
public class 二叉树根节点到叶子节点和为指定值的路径 {
//递归解法
public ArrayList<ArrayList<Integer>> pathSum1(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
dfs1(root, sum, new ArrayList<>(), result);
return result;
}
//非递归解法
public ArrayList<ArrayList<Integer>> pathSum2(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.isEmpty()){
TreeNode node = stackNode.pop();
ArrayList<Integer> tempList = stackList.pop();
if(node.left == null && node.right == null && node.val == sum){
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;
}
public void dfs1(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(root.val);
//如果到达叶子节点,就不能往下走了,直接return
if(root.left == null && root.right == null){
//如果到达叶子节点,并且sum等于叶子节点的值,说明我们找到了一组,要把它放到result中
if(sum == root.val){
result.add(subList);
}
//到叶子节点之后直接返回
return;
}
//如果没有到达叶子节点,就继续从他的两个左右子节点往下找,注意到下一步的时候,sum要减去当前节点的值
dfs1(root.left, sum - root.val, subList, result);
dfs1(root.right, sum - root.val, subList, result);
}
public void dfs2(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值要减去当前节点的值
dfs2(root.left, sum - root.val, list, result);
dfs2(root.right, sum - root.val, list, result);
//我们要理解递归的本质,当递归往下传递的时候他最后还是会往回走,
//我们把这个值使用完之后还要把它给移除,这就是回溯
list.remove(list.size() - 1);
}
}