找树左下角的值

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);
        }
    }

从中序与后序遍历序列构造二叉树