leecode no.113 路径总和 II

package tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
* 113. 路径总和 II
* 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
*
* 叶子节点 是指没有子节点的节点。
*
* @author Tang
* @date 2021/7/16
*/
public class PathSum {

int targetSum;

List<List<Integer>> lists = new ArrayList<>();

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root == null){
return lists;
}
this.targetSum = targetSum;
preSearch(root, 0, new Stack<>());
return lists;
}

/**
* 继续前序遍历
*/
private void preSearch(TreeNode node, int sum, Stack<Integer> stack){
if(node == null){
return;
}
sum += node.val;
stack.push(node.val);
if(node.left == null && node.right == null){
if(sum == targetSum){
List<Integer> list = new ArrayList<>(stack);
lists.addAll(Collections.singleton(list));
return;
}
}
if(node.left != null){
preSearch(node.left, sum, stack);
stack.pop();
}
if(node.right != null){
preSearch(node.right, sum, stack);
stack.pop();
}
}

public static void main(String[] args) {

}

}
上一篇:2021年12月22日 笔记


下一篇:JZ63 数据流中的中位数