代码随想录刷题学习日记

仅为个人记录复盘学习历程，解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

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

根据一棵树的中序遍历与后序遍历构造二叉树,假设树中没有重复的元素。

提供参数：中序遍历数组inorder，后序遍历数组postorder

主要操作：

递归三要素

1.返回值类型和参数：

由于需要构造二叉树，返回值类型为节点，参数为中序遍历数组inorder，后续遍历数组postorder。

2.终止条件：

当后续遍历数组postorder没有数据时返回null

3.单层递归逻辑：

获取节点

构造节点

如果当前构造节点是叶节点直接返回

如果并不是叶节点，为下一次递归准备数据

获取分界点索引，分割中序遍历数组，构造左子中序遍历数组，右子中序遍历数组。

舍弃末尾元素，分割后续遍历数组，构造左子后续遍历数组，右子后续遍历数组。（根据索引，根据数据个数）

继续遍历左子中序遍历数组，左子后续遍历数组。

继续遍历右子中序遍历数组，右子后续遍历数组。

代码大致如下：

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length==0||postorder.length==0)return null;

        List<Integer>inorderList=new ArrayList<>();
        List<Integer>postorderList=new ArrayList<>();
        for(int i=0;i<inorder.length;i++){
            inorderList.add(inorder[i]);
            postorderList.add(postorder[i]);
        }
        return traversal(inorderList,postorderList); 
        
    }
    public TreeNode traversal(List<Integer>inorder,List<Integer>postorder){
        //终止条件
        if(postorder.size()==0)return null;
        //单层递归逻辑
        //获取后续遍历最后一个元素作为中序遍历的分界点
        int deleteNum=postorder.get(postorder.size()-1);
        //构造节点
        TreeNode node=new TreeNode(deleteNum);
        //如果为叶节点，直接将该结点返回
        if(postorder.size()==1)return node;
        //不为叶节点，分割数组
        //分割中序遍历数组
        int deleteIndex=0;
        for(int i=0;i<inorder.size();i++){
            if(inorder.get(i)==deleteNum){
                deleteIndex=i;
                break;
            }
        }
        //左闭右开
        List<Integer>leftinorder=inorder.subList(0,deleteIndex);
        List<Integer>rightinorder=inorder.subList(deleteIndex+1,inorder.size());

        List<Integer>leftpostorder=postorder.subList(0,deleteIndex);
        List<Integer>rightpostorder=postorder.subList(deleteIndex,inorder.size()-1);

        node.left=traversal(leftinorder,leftpostorder);
        node.right=traversal(rightinorder,rightpostorder);
        return node;
    }

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

根据一棵树的前序遍历与中序遍历构造二叉树，你可以假设树中没有重复的元素。

提供参数：先序遍历数组preorder，中序遍历数组inorder

主要操作：

与上题类似，不同之处在于后序遍历数组换成了前序遍历数组，遍历需要从前开始，构造数组时也按照前序遍历数组的来即可。

代码大致如下：

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null)return null;
        List<Integer>preorderList=new ArrayList<>();
        List<Integer>inorderList=new ArrayList<>();
        for(int i=0;i <preorder.length;i++){
            preorderList.add(preorder[i]);
            inorderList.add(inorder[i]);
        }
        return traversal(preorderList,inorderList);
    }
    public TreeNode traversal(List<Integer>preorder,List<Integer>inorder){
        if(preorder.size()==0)return null;
        int deleteNum=preorder.get(0);
        TreeNode node=new TreeNode(deleteNum);
        int deleteIndex=0;
        if(preorder.size()==1)return node;
        for(int i=0;i<inorder.size();i++){
            if(inorder.get(i)==deleteNum){
                deleteIndex=i;
                break;
            }
        }
        List<Integer>leftInorder=inorder.subList(0,deleteIndex);
        List<Integer>rightInorder=inorder.subList(deleteIndex+1,inorder.size());
        List<Integer>leftPreorder=preorder.subList(1,deleteIndex+1);
        List<Integer>rightPreorder=preorder.subList(deleteIndex+1,preorder.size());
        node.left=traversal(leftPreorder,leftInorder);
        node.right=traversal(rightPreorder,rightInorder);
        return node;
    }