题目链接:113. Path Sum II
题目描述
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
简而言之,就是在上一个问题基础上 输出路径
Example:
Given the below binary tree and sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Return:
[
[5,4,11,2],
[5,8,4,5]
]
解题思路
上一题只需要判断即可,这一个需要找出值为SUM的路径,我们需要一个数据结构来存储遍历过程的路径。
以5-4-11-7路径为例,其和不等于22,那么需要后退到5-4-11,然后再进入有节点5-4-11-2,其和为22,且2是叶子结点,则输出路径。很自然联想到使用栈这种结构,当和满足时输出栈内元素,如果不满足,则栈顶出栈。
题解
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
if(root == null) return result;
Stack<TreeNode> stack = new Stack<>();
findPath(root,result,stack,sum);
return result;
}
public void findPath(TreeNode root,List<List<Integer>> result,Stack<TreeNode> stack,int sum){
if(root == null) return;
stack.push(root);
int temp = sum - root.val;
// 是叶子结点,其算上叶子结点之后的和为SUM
if(root.left == null && root.right==null && temp==0){
List<Integer> cur = new ArrayList<>();
for(TreeNode t:stack){
cur.add(t.val);
}
result.add(cur);
}
if(root.left!=null)
findPath(root.left,result,stack,temp);
if(root.right!=null)
findPath(root.right,result,stack,temp);
stack.pop();
}
网友评论