day18

1、leetcode513 找树左下角的值

1. 递归法

   1. 目标：在树的最后一行找到最左边的值

      1. 保证优先左边搜索，【前中后序都可以，因为没有中间节点的处理逻辑】
      2. 然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

   2. 递归三部曲：

      1. 确定递归函数的参数和返回值
         1. 参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。
      2. 确定终止条件
         1. 当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。
      3. 确定单层递归的逻辑
         1. 在找最大深度的时候，递归的过程中依然要使用回溯，

   3. 代码实现

      class Solution {
          private int maxDepth = Integer.MIN_VALUE;//记录最大深度
          private int res = 0;//记录最大深度最左节点的数值
      	
          //找深度最大的叶子节点，确保优先左边遍历
          public void traversal(TreeNode root, int depth){
              if(root.left == null && root.right == null){
                  if(depth > maxDepth){
                  maxDepth = depth;
                  res = root.val;
                  }
                  return;
              }
      
              if(root.left!=null){
                  traversal(root.left, depth+1);
              }
      
              if(root.right!=null){
                  traversal(root.right, depth+1);
              }
      
              return;
      
          }
      
          public int findBottomLeftValue(TreeNode root) {
              traversal(root, 0);
              return res;
          }
      }
      

2. 迭代法【层序遍历】【找到最后一层的第一个元素】

   class Solution {
       public int findBottomLeftValue(TreeNode root) {
           Queue<TreeNode> que = new LinkedList<TreeNode>();
           int res = 0;
   
           if(root != null){
               que.offer(root);
           }
   
           while(!que.isEmpty()){
               int size = que.size();
   
               for(int i=0; i<size; i++){
                   TreeNode node = que.poll();
                   if(i==0){
                       res = node.val;//记录每层第一个元素，最后值为最后一层的第一个元素值
                   }
                   if(node.left!=null){
                       que.offer(node.left);
                   }
                   if(node.right!=null){
                       que.offer(node.right);
                   }
               }
           }
   
           return res;
       }
   }
   

2、leetcode112 路径总和

1. 递归法

   1. 代码实现

      class Solution {
          public boolean hasPathSum(TreeNode root, int targetSum) {
              if(root == null){
                  return false;
              }
              targetSum -= root.val;
      
              if(root.left==null && root.right==null){//root为叶子节点
                  return targetSum==0;
              }
      
              if(root.left!=null){//从左子树找到路径
                  if(hasPathSum(root.left, targetSum)){
                      return true;
                  }
              }
      
              if(root.right!=null){//从右子树找到路径
                  if(hasPathSum(root.right, targetSum)){
                      return true;
                  }
              }
      
              return false;
          }   
      }
      

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

1. 步骤

   1. 第一步：如果后序/中序数组大小为零的话，说明是空节点了。

   2. 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

      • 因为后序是左右中，能够最后一个元素确定root节点

   3. 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

   4. 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

      • 通过root.val切割中序数组

   5. 第五步：切割后序数组，切成后序左数组和后序右数组

      • 通过中序左数组的长度切割后序数据【因此只能先切割中序数组】

      注意：切割标准统一，例如：均为左闭右开形式

   6. 第六步：递归处理左区间和右区间

2. 代码实现

   class Solution {
       public TreeNode buildTree(int[] inorder, int[] postorder) {
           if(postorder.length == 0){
               return null;
           }
   
           TreeNode root = new TreeNode(postorder[postorder.length-1]);
           if(postorder.length == 1){
               return root;
           }
   
           int index = 0;
           for(index = 0; index<inorder.length; index++){
               if(inorder[index] == root.val){
                   break;
               }
           }
   
           int[] leftInorder = Arrays.copyOfRange(inorder,0,index);
           int[] rightInorder = Arrays.copyOfRange(inorder,index+1,inorder.length);
   
           postorder = Arrays.copyOfRange(postorder,0,postorder.length-1);
           int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);
           int[] rightPostorder = Arrays.copyOfRange(postorder, leftInorder.length, postorder.length);
   
           root.left = buildTree(leftInorder, leftPostorder);
           root.right = buildTree(rightInorder, rightPostorder);  
   
           return root;
       }
   

4、leetcode105 从前序与中序遍历序列构造二叉树

1. 思路与上一题一致

2. 代码实现

   class Solution {
       public TreeNode buildTree(int[] preorder, int[] inorder) {
           if(preorder.length == 0){
               return null;
           }
   
           TreeNode root = new TreeNode(preorder[0]);
           if(preorder.length == 1){
               return root;
           }
   
           int index = 0;
           for(index = 0; index<inorder.length; index++){
               if(inorder[index] == root.val){
                   break;
               }
           }
   
           int[] leftInorder = Arrays.copyOfRange(inorder,0,index);
           int[] rightInorder = Arrays.copyOfRange(inorder,index+1,inorder.length);
   
           preorder = Arrays.copyOfRange(preorder,1,preorder.length);
           int[] leftPretorder = Arrays.copyOfRange(preorder, 0, leftInorder.length);
           int[] rightPretorder = Arrays.copyOfRange(preorder, leftInorder.length, preorder.length);
   
           root.left = buildTree(leftPretorder, leftInorder);
           root.right = buildTree(rightPretorder, rightInorder);  
   
           return root;
       }
   }