二叉树中和为某一值的路径
输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
样例
给出二叉树如下所示,并给出num=22。
5
/ \
4 6
/ / \
12 13 6
/ \ / \
9 1 5 1
输出:[[5,4,12,1],[5,6,6,5]]
算法1
书上的前序遍历思路+剪枝优化
时间复杂度O(N)
java 代码
class Solution {
public List<List<Integer>> findPath(TreeNode root,int sum){
List<List<Integer>> lists=new ArrayList<>();
Stack<Integer> path=new Stack<>();
int currentSum=0;
if(root==null)
return lists;
findPath(lists,root,sum,path,currentSum);
return lists;
}
public void findPath(List<List<Integer>> res,TreeNode node,int sum,Stack<Integer> path,int currentSum){
//加上当前值进行判断
currentSum+=node.val;
path.push(node.val);
//如果是叶节点,并且当前路径的和等于输入的值
//则把这条路径保存到lists结果集中
boolean isLeaf=node.left==null&&node.right==null;
if(currentSum==sum&&isLeaf){
List<Integer> list=new ArrayList<>();
//从顶到底遍历栈
for(int i:path){
list.add(i);
}
res.add(list);
}
//如果不是叶节点,遍历他的子节点
//可以加入剪枝:如果当前和大于等于输入,舍弃这一支
//因为题目要求的路径是从根节点到叶子节点的一条路径
//所以还没有到叶子节点就超过或者等于sum的情况就可以舍去
if(node.left!=null&¤tSum<sum)
findPath(res,node.left,sum,path,currentSum);
if(node.right!=null&¤tSum<sum)
findPath(res,node.right,sum,path,currentSum);
//返回根节点时改回currentSum,栈弹出当前的值
currentSum-=node.val;
path.pop();
}
}