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

目录

• 一、力扣513.找树左下角的值
• • 1.1 题目
  • 1.2 思路
  • 1.3 代码
  • 1.4 总结
  • 二、力扣112.路径总和
  • • 2.1 题目
    • 2.2 思路
    • 2.3 代码
    • 2.4 总结
    • 三、力扣113.路径总和二
    • • 3.1 题目
      • 3.2 思路
      • 3.3 代码
      • 3.4 总结
      • 四、力扣106.从中序与后序遍历序列构造二叉树
      • • 4.1 题目
        • 4.2 思路
        • 4.3 代码
        • 4.4 总结
        • 五、力扣105.从前序与中序遍历序列构造二叉树
        • • 5.1 题目
          • 5.2 思路
          • 5.3 代码
          • 5.4 ���结

            一、力扣513.找树左下角的值

            1.1 题目

            1.2 思路

            迭代

            我的思路：层序遍历，寻找最后一层的第一个值，可以用一个集合记录每一层的第一个节点的数值，遍历结束后输出集合的最后一个值。

            递归+回溯

            1.确定递归函数的参数和返回值

            参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void。

            本题还需要类里的两个全局变量，maxLen用来记录最大深度，result记录最大深度最左节点的数值。

            2.确定终止条件

            当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。

            3.确定单层递归的逻辑

            在找最大深度的时候，递归的过程中依然要使用回溯。

            1.3 代码

            迭代

            class Solution {    public int findBottomLeftValue(TreeNode root) {        //迭代法，层序遍历        Queue que = new LinkedList();        List res = new ArrayList();        if(root == null){            return root.val;        }        que.offer(root);        while(!que.isEmpty()){            int size = que.size();            int startSize = size;            while(size > 0){                TreeNode cur =  que.poll();                if(size == startSize){                    res.add(cur.val);                }                if(cur.left != null){                    que.offer(cur.left);                }                if(cur.right != null){                    que.offer(cur.right);                }                size--;                            }        }        return res.get(res.size()-1);    }}

            递归

            class Solution {    private int maxDepth = Integer.MIN_VALUE;    private int result;    public int findBottomLeftValue(TreeNode root) {        if(root.left == null && root.right == null){            return root.val;        }        traversal(root,1);        return result;    }    //递归+回溯  前序遍历，因为优先向左遍历    public void traversal(TreeNode node,int depth){        //确定递归的终止条件        if(node.left == null && node.right == null){            if(depth > maxDepth){                maxDepth = depth;                result = node.val;            }            return;        }        if(node.left != null){            depth++;            traversal(node.left,depth);            depth--;        }        if(node.right != null){            depth++;            traversal(node.right,depth);            depth--;        }    }}

            1.4 总结

            递归+回溯的思路比较难，后序还需要加强掌握。

            二、力扣112.路径总和

            2.1 题目

            2.2 思路

            自己的思路：感觉和二叉树的所有路径那道题的思路一样！递归+回溯。

            本题思路：不需要像求所有路径那道题一样把所有路径都求出来，因为本题只是问是否存在这样的一条路径，所以当我们发现了这样的一条路径时，直接返回即可，不需要再遍历了。

            2.3 代码

            自己的思路（代码提交不通过，已解决）

            注意：Java集合中存储的是引用类型的数据，所以当集合中要再存入一个集合时，每次要new一个新的集合，不能多次add同一个集合（比如result里add路径集合path3次，这样会造成此时数组中就有三个相同的地址，地址相同，指向的对象自然也相同，所以此刻List集合中的三个对象其实都是指向了同一个path，而且值均为最新的赋值。）

            出问题的代码：

            class Solution {    public boolean hasPathSum(TreeNode root, int targetSum) {        List path = new ArrayList();        List res = new ArrayList();        if(root == null){            return false;        }         traversal(root,path,res);         for(int i =0;i             List                 sum += p.get(j);             }             if(sum == targetSum){                 return true;             }         }         return false;    }    //前序遍历  递归+回溯    public void traversal(TreeNode node,List        path.add(node.val);        //确定终止条件        if(node.left == null && node.right == null){            res.add(path);//！！！！！！这里的问题！！！！！！！            return;        }        //前序遍历        if(node.left != null){            traversal(node.left,path,res);            path.remove(path.size()-1);        }        if(node.right != null){            traversal(node.right,path,res);            path.remove(path.size()-1);        }    }}    public boolean hasPathSum(TreeNode root, int targetSum) {        List            return false;        }         traversal(root,path,res);         for(int i =0;i             List                 sum += p.get(j);             }             if(sum == targetSum){                 return true;             }         }         return false;    }    //前序遍历  递归+回溯    public void traversal(TreeNode node,List        path.add(node.val);        //确定终止条件        if(node.left == null && node.right == null){            res.add(new ArrayList            traversal(node.left,path,res);            path.remove(path.size()-1);        }        if(node.right != null){            traversal(node.right,path,res);            path.remove(path.size()-1);        }    }}    public boolean hasPathSum(TreeNode root, int targetSum) {        if(root == null){            return false;        }        return traversal(root,targetSum);    }    //递归+回溯  前序遍历    public boolean traversal(TreeNode node,int count){        count -= node.val;        //确定终止条件        if(node.left == null && node.right == null && count == 0){            return true;        }        if(node.left == null && node.right == null && count != 0){            return false;        }        //前序遍历        if(node.left != null){           boolean b =  traversal(node.left,count);           if(b){               return true;           }        }        if(node.right != null){           boolean a =  traversal(node.right,count);           if(a){               return true;           }        }        return false;    }}    public List        List            return res;        }        traversal(root,path,res,targetSum);        return res;    }    //递归 前序遍历 与上题不同的是找出所有，所以必须遍历整棵树    public void traversal(TreeNode node,List        count -= node.val;        path.add(node.val);        //确定终止条件,叶子结点        if(node.left == null && node.right == null && count == 0){            res.add(new ArrayList            return;        }        //前序遍历        if(node.left != null){            traversal(node.left,path,res,count);            path.remove(path.size()-1);//回溯        }        if(node.right != null){            traversal(node.right,path,res,count);            path.remove(path.size()-1);//回溯        }    }}    //利用hashmap保存中序数组数值及其下标，方便查询    public Map        hashmap =  new HashMap            hashmap.put(inorder[i],i);        }        return findNode(inorder,0,inorder.length,postorder,0,postorder.length);    }    //形参：中序数组，起始下标，终止下标；后序数组，起始下标，终止下标；注意均保持左闭右开    public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){        //确定终止条件        if(inBegin = inEnd || postBegin = postEnd){            return null;        }        //根据后序遍历的最后一个节点(根节点)来分割中序遍历数组        int rootIndex = hashmap.get(postorder[postEnd-1]);        TreeNode root = new TreeNode(inorder[rootIndex]);        //中序数组根节点左边的元素个数        int inLeftLength = rootIndex - inBegin;        root.left = findNode(inorder,inBegin,inBegin+inLeftLength,postorder,postBegin,postBegin+inLeftLength);        root.right = findNode(inorder,rootIndex+1,inEnd,postorder,postBegin+inLeftLength,postEnd-1);        return root;    }}    public Map        //类似于从后序与中序遍历序列构造二叉树        hashmap = new HashMap            hashmap.put(inorder[i],i);        }        return findNode(preorder,0,preorder.length-1,inorder,0,inorder.length-1);        }    //区间保持左闭右闭    public TreeNode findNode(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){        if(preBegin  preEnd || inBegin  inEnd){            return null;        }         int rootIndex = hashmap.get(preorder[preBegin]);         TreeNode root = new TreeNode(inorder[rootIndex]);         int inLeftLength = rootIndex - inBegin;         root.left = findNode(preorder,preBegin+1,preBegin+inLeftLength,inorder,inBegin,rootIndex-1);         root.right =findNode(preorder,preBegin+inLeftLength+1,preEnd,inorder,rootIndex+1,inEnd);         return root;    }}