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

前言

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

递归三部曲

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

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

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

题目讲解

逻辑上已经懂了视频里讲的用的是C++ 与java逻辑相同但代码实现却不一样
java通过HashMap来实现

一共分六部来实现

代码就不写了 自己没整出来