标签：node res List part04 DAY14 二叉树 path null root
找树左下角的值
513. 找树左下角的值
class Solution {
public List<List<Integer>> reList=new ArrayList<>();
public int findBottomLeftValue(TreeNode root) {
check(root);
int index=reList.size()-1;
return reList.get(index).get(0);
}
public void check(TreeNode node)
{
if(node==null)
{
return ;
}
Queue<TreeNode> qe=new LinkedList<>();
qe.offer(node);
while(!qe.isEmpty())
{
List<Integer> itemlist=new ArrayList<>();
int lens=qe.size();
while(lens>0)
{
TreeNode tmp=qe.poll();
itemlist.add(tmp.val);
if(tmp.left!=null)
{
qe.offer(tmp.left);
}
if(tmp.right!=null)
{
qe.offer(tmp.right);
}
lens--;
}
reList.add(itemlist);
}
}
}
路径总和
112. 路径总和
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
if(root.left==null&&root.right==null)
{
return targetSum==root.val;
}
int newTargetSum=targetSum-root.val;
return hasPathSum(root.left, newTargetSum) || hasPathSum(root.right, newTargetSum);
}
}
- 方法二：求所有路径并判断每条路径的和是否存在等于目标和
class Solution {
public List<List<Integer>> res=new ArrayList<>();
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
List<Integer> path=new ArrayList<>();
traversal(root,path,res);
for(int i=0;i<res.size();i++)
{
int Sum=0;
for(int j=0;j<res.get(i).size();j++)
{
Sum+=res.get(i).get(j);
}
if(Sum==targetSum) return true;
}
return false;
}
private void traversal(TreeNode node,List<Integer> path,List<List<Integer>> res)
{
//if(node==null) return;
path.add(node.val);
if(node.left==null&& node.right==null)//叶子节点
{
res.add(new ArrayList<>(path));
path.remove(path.size() - 1); // 回溯：移除当前节点，恢复路径到上一个状态
return ;
}
if(node.left!=null)
{
traversal( node.left, path,res);
}
if(node.right!=null)
{
traversal( node.right, path,res);
}
path.remove(path.size()-1);
}
}
路径总和II
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>(); // 用于存储所有满足条件的路径
List<Integer> path = new ArrayList<>();
findPaths(root, targetSum, path, res);
return res;
}
private void findPaths(TreeNode node, int targetSum, List<Integer> path, List<List<Integer>> res) {
if (node == null) return; // 如果当前节点为空，直接返回
// 添加当前节点到路径中
path.add(node.val);
// 如果当前节点是叶子节点，检查路径和是否等于目标和
if (node.left == null && node.right == null && targetSum == node.val) {
res.add(new ArrayList<>(path)); // 保存路径的副本
} else {
// 递归检查左子树和右子树
findPaths(node.left, targetSum - node.val, path, res);
findPaths(node.right, targetSum - node.val, path, res);
}
// 回溯：移除当前节点，恢复路径到上一个状态
path.remove(path.size() - 1);
}
}
class Solution {
public List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root==null)
return null;
List<Integer> path=new ArrayList<>();
traversal(root,path,res);
// 只保留满足条件的路径
List<List<Integer>> validPaths = new ArrayList<>();
for(int i=0;i<res.size();i++)
{
int Sum=0;
for(int j=0;j<res.get(i).size();j++)
{
Sum+=res.get(i).get(j);
}
if(Sum==targetSum)
{
validPaths.add(res.get(i));
}
}
return validPaths;
}
private void traversal(TreeNode node,List<Integer> path,List<List<Integer>> res)
{
// if(node==null) return;
path.add(node.val);
if(node.left==null&& node.right==null)//叶子节点
{
res.add(new ArrayList<>(path));
path.remove(path.size() - 1); // 回溯：移除当前节点，恢复路径到上一个状态
return ;
}
if(node.left!=null)
{
traversal( node.left, path,res);
}
if(node.right!=null)
{
traversal( node.right, path,res);
}
path.remove(path.size()-1);
}
}
从中序与后序遍历序列构造二叉树
标签：node,
res,
List,
part04,
DAY14,
二叉树,
path,
null,
root
From： https://www.cnblogs.com/FreeDrama/p/18411281