剑指 Offer 34. 二叉树中和为某一值的路径
Offer_34
题目详情
题解分析
- 本题是二叉树相关的题目，但是又和路径记录相关。
在记录路径时，可以使用一个栈来存储一条符合的路径，在回溯时将进栈的元素出栈，以此可以找到所有的Path。
package com.walegarrett.offer;
import java.util.*;
/**
* @Author WaleGarrett
* @Date 2021/2/1 18:09
*/
/**
* 题目：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
* 从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
*/
public class Offer_34 {
int sum;
Stack<Integer> sta = new Stack<>();
List<List<Integer>> allPaths;
void dfs(TreeNode now, int num){
if(now == null)//这里不能加上num > sum 因为可能存在负数的情况
return;
else if(now.left == null && now.right == null){
if(num == sum){
// 打印
List<Integer> current = Arrays.asList(sta.toArray(new Integer[sta.size()]));
// Collections.reverse(current);
allPaths.add(current);
}
return;
}
if(now.left != null){
sta.push(now.left.val);
dfs(now.left, num + now.left.val);
sta.pop();
}
if(now.right != null){
sta.push(now.right.val);
dfs(now.right, num + now.right.val);
sta.pop();
}
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null)
return new ArrayList<>();
this.sum = sum;
allPaths = new ArrayList<>();
sta.push(root.val);
dfs(root, root.val);
return allPaths;
}
}
