当前位置：首页 > news >正文

代码随想录算法训练营第十八天二叉树 java : .106 从中序与后序遍历序列构造二叉树113. 路径总和ii 112 路径总和 513.找树左下角的值

news 来源：原创 2024/11/15 15:33:54

文章目录

前言
LeetCode 513.找树左下角的值
- 题目讲解
- 思路
- - - 那么如何找最左边的呢？
Leetcode 112 路径总和
- 题目讲解
LeetCode 113. 路径总和ii
- 题目讲解
Leetcode 106 从中序与后序遍历序列构造二叉树
- 题目讲解

前言

人的不幸在于他们不想走自己的那条路，总想走别人的路。

递归三部曲

确定递归函数的参数和返回值
确定终止条件
确定单层递归的逻辑

LeetCode 513.找树左下角的值

题目讲解

思路

最左边的值不一定非得是左孩子

因为没有中间的处理逻辑所以前中后序都可以

那么如何找最左边的呢？

可以使用前序遍历（当然中序，后序都可以，因为本题没有中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
     private int Deep = -1;
     private int value =0;
    public int findBottomLeftValue(TreeNode root) {
          value =root.val;
          findLeftValue (root,0);
          return value;
    }
    //这块如果是 int 就会造成 返回类型错误
    private void findLeftValue(TreeNode root,int deep)
    {
        if(root== null) return;    
        if( root.left ==null && root.right ==null)
        {
            if( deep>Deep)
            {
                value =root.val;
                Deep =deep;
            }
        }
    
    if( root.left!=null) findLeftValue(root.left,deep+1);
    
    if( root.right!=null) findLeftValue(root.right,deep+1);
    
    
    }
    
    }

Leetcode 112 路径总和

题目讲解

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if( root ==null)
        {
            return false;
        }
         targetSum -= root.val;

         //叶子节点
         if( root.left ==null && root.right==null)
         {
              return targetSum ==0;
         }

         //左
         if( root.left!=null)
         {
             boolean left =hasPathSum(root.left,targetSum);
             if( left)
             {
                 return true;
             }
             
         }
         //右
         if( root.right!=null)
         {
             boolean right = hasPathSum(root.right,targetSum);
             if( right)
             {
                 return true;
             }
         }
         return false;
    }
}

LeetCode 113. 路径总和ii

题目讲解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
      List<List<Integer>> res =new ArrayList<>();
      if( root ==null) return res;
      List<Integer> path = new LinkedList<>();
      preorder( root,targetSum,res,path);
      return res;
    }
    public void preorder( TreeNode root,int targetSum,List<List<Integer>> res,List<Integer> path)
    {
        path.add(root.val);
        if( root.left ==null && root.right ==null)
        {
            if( targetSum- root.val==0)
            {
                res.add(new ArrayList<>(path));
            }
            return;
        }
    
    

    if(root.left !=null)
    {
          preorder(root.left,targetSum-root.val,res,path);        
          path.remove( path.size()-1);            
    }
    if( root.right!=null)
    {
         preorder(root.right,targetSum-root.val,res,path);       
         path.remove(path.size()-1);
    }
}
}