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

513.找树左下角的值

• 刷题https://leetcode.cn/problems/find-bottom-left-tree-value/description/
• 文章讲解https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html
• 视频讲解https://www.bilibili.com/video/BV1424y1Z7pn/?vd_source=af4853e80f89e28094a5fe1e220d9062

• 题解1（迭代法）：

  /** * 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 int findBottomLeftValue(TreeNode root) {        Queue queue = new LinkedList();        queue.offer(root);        int result = 0;        while(!queue.isEmpty()){            //记录当前遍历层的元素的个数，保证层序遍历            int size = queue.size();            for(int i = 0;i  

  • 题解2（递归法）：

    /** * 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 {    //递归法    //记录当前最大深度    int DEEP = -1;    //记录当前最大深度结点    int value = 0;    public int findBottomLeftValue(TreeNode root) {        value = root.val;        findLeftValue(root, 0);        return value;    }    public void findLeftValue(TreeNode root,int deep){        //递归出口        if(root == null){            return;        }        //若遍历到叶子结点且该结点深度为目前最大，则更新DEEP和value        if(root.left == null && root.right == null){            if(deep > DEEP){                value = root.val;                DEEP = deep;            }        }        //左处理        if(root.left != null){            deep += 1;            //递归            findLeftValue(root.left, deep);            //回溯            deep -= 1;            //此三行的简写形式            // findLeftValue(root.left, deep + 1);        }        //右处理        if(root.right != null){            deep += 1;            findLeftValue(root.right, deep);            deep -= 1;            //此三行的简写形式            // findLeftValue(root.right, deep + 1);        }    }}

    112. 路径总和

    • 刷题https://leetcode.cn/problems/path-sum/description/
    • 文章讲解https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
    • 视频讲解https://www.bilibili.com/video/BV19t4y1L7CR/?vd_source=af4853e80f89e28094a5fe1e220d9062

    • 题解（递归法）：

      /** * 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 {    //递归    List result;    LinkedList path;    public boolean hasPathSum(TreeNode root, int targetSum) {        result = new LinkedList();        path = new LinkedList();        travesal(root, targetSum);        return !result.isEmpty();    }     public void travesal(TreeNode root, int count){        //递归结束返回        if(root == null){            return;        }        //路径中加入根结点        path.offer(root.val);        //处理加入结点的值        count -= root.val;        //若在某条路径中到叶子结点时count已经减为0，        //则说明这条路路径总和符合要求        if(root.left == null && root.right == null && count == 0){            //将当前path路径列表加入最终结果列表            result.add(new LinkedList(path));        }        //递归处理        //左处理        travesal(root.left, count);        //右处理        travesal(root.right, count);        //回溯处理        path.removeLast();        //中无需处理，因为不对中操作    }}

      113.路径总和ii

      • 刷题https://leetcode.cn/problems/path-sum-ii/description/
      • 文章讲解https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
      • 视频讲解https://www.bilibili.com/video/BV19t4y1L7CR/?vd_source=af4853e80f89e28094a5fe1e220d9062

      • 题解（递归法）：

        /** * 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 {    //递归    List result;    // LinkedList作为Queue的实现类使用offer方法    LinkedList path;    public List pathSum(TreeNode root, int targetSum) {        result = new LinkedList();         path = new LinkedList();        travesal(root, targetSum);        return result;    }    public void travesal(TreeNode root, int targetSum){        if(root == null){            return;        }        path.offer(root.val);        targetSum -= root.val;        if(root.left == null && root.right == null && targetSum == 0){            result.add(new LinkedList(path));        }        travesal(root.left, targetSum);        travesal(root.right, targetSum);        path.removeLast();    }}

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

        • 刷题https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
        • 文章讲解https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html
        • 视频讲解https://www.bilibili.com/video/BV1vW4y1i7dn/?vd_source=af4853e80f89e28094a5fe1e220d9062

        • 题解（递归法）：

          /** * 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 {    //中序后序构造二叉树    //使用Map结构，方便根据数值查找位置    Map map;    public TreeNode buildTree(int[] inorder, int[] postorder) {        map = new HashMap();        //使用Map存储中序序列数值        for(int i = 0; i = inEnd || postBegin >= postEnd){            return null;        }        //步骤1：找到后序遍历最后一个元素在中序遍历中的位置，对中序遍历做切割        //获取当前根结点在中序序列中对应的下标        int rootIndex = map.get(postorder[postEnd - 1]);        //用中序遍历的中结点构造出新二叉树的根结点        TreeNode root = new TreeNode(inorder[rootIndex]);        //步骤2：用中序遍历切割后的中序前半序列的长度对后序遍历序列做切割        //获得中序前半序列的长度        int lenOfLeft = rootIndex - inBegin;                //步骤3：用中序序列切割后的前半序列和后序序列切割后的前半序列进行再一次的递归        //下同，用中序序列切割后的后半序列和后序序列切割后的后半序列进行再一次的递归        root.left = findNode(inorder, inBegin, rootIndex,                                postorder, postBegin, postBegin + lenOfLeft);        //debug点：这里的容器为左闭右开，需要根据左闭右开设置递归边界                //为保证序列连续性，inorder开始需要+1                //postEnd - 1,加上左闭右开，因为要空出来这一趟后序遍历挑出来的root切割点                //中序遍历的切割点也通过rootIndex和rootIndex + 1的左闭右开设置在rootIndex位置做了切割        root.right = findNode(inorder, rootIndex + 1, inEnd,                                postorder, postBegin + lenOfLeft, postEnd - 1);                //步骤4：root结点已定义，root.left,root.right均已通过递归确定，        //可以返回root代表重新构建的二叉树        return root;    }}

          105.从前序与中序遍历序列构造二叉树

          • 刷题https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
          • 文章讲解https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html
          • 视频讲解https://www.bilibili.com/video/BV1vW4y1i7dn/?vd_source=af4853e80f89e28094a5fe1e220d9062

          • 题解（递归法）

             （目前执行出错，错误信息如下）

            java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5

            /** * 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 {    //前序中序遍历序列构造二叉树    Map map;    public TreeNode buildTree(int[] preorder, int[] inorder) {        map = new HashMap();        for(int i = 0; i = inEnd || preBegin >= preEnd){            return null;        }        //步骤1：根据前序遍历确定root来切割中序序列        int rootIndex = map.get(preorder[preBegin]);        //存储这一轮找出的根结点        TreeNode root = new TreeNode(inorder[rootIndex]);        //步骤2：用前序序列切割出来的前半序列的长度对中序序列进行切割        int lenOfLeft = rootIndex - inBegin;        //步骤3：递归root的左孩子和右孩子(左闭右开)        //挖去当前根结点，对左右子树进行处理        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft,                                 inorder, inBegin, rootIndex);        root.right = findNode(preorder, preBegin + lenOfLeft, preEnd,                                inorder, rootIndex + 1, inEnd);                return root;    }}

            • 题解（递归法）：

              （Bug已解决，原因：由于前序序列已经确定出root，所以preBegin和preEnd都应该向后加一）

              /** * 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 {    //前序中序遍历序列构造二叉树    Map map;    public TreeNode buildTree(int[] preorder, int[] inorder) {        map = new HashMap();        for(int i = 0; i = inEnd || preBegin >= preEnd){            return null;        }        //步骤1：根据前序遍历确定root来切割中序序列        int rootIndex = map.get(preorder[preBegin]);        //存储这一轮找出的根结点        TreeNode root = new TreeNode(inorder[rootIndex]);        //步骤2：用前序序列切割出来的前半序列的长度对中序序列进行切割        int lenOfLeft = rootIndex - inBegin;        //步骤3：递归root的左孩子和右孩子(左闭右开)        //挖去当前根结点，对左右子树进行处理        //debug点：由于前序序列已经确定出root，所以preBegin和preEnd都应该向后加一        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,                                 inorder, inBegin, rootIndex);        root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,                                inorder, rootIndex + 1, inEnd);                return root;    }}