LeetCode 从前序和中序遍历序列构造二叉树/根据前序和后续遍历构造二叉树-一一网

这是我参与更文挑战的第 30 天，活动详情查看：更文挑战

从前序和中序遍历序列构造二叉树（105）

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
复制代码

返回如下的二叉树：

思路分析

根据前序遍历的顺序和中序遍历的顺序找出我们的原始二叉树，首先我们需要知道前序遍历的特点，根节点是在数组的第一个位置，而中序遍历的话，根节点是在中间（如果左边有数据）。我们可以分别为 preorder 数组和 inorder 数组分别区分出左侧二叉树和右侧二叉树对应的索引。

然后取出根节点，左边的节点根据preorder和inorder位置对应的索引，右侧也是如此。

代码展示

解法一：

public TreeNode buildTree(int[] preorder, int[] inorder) {
        return myBuildTree(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);
    }

    private TreeNode myBuildTree(int[] preorder,int i,int j,int[] inorder,int p,int r){
        if(i > j){
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);
        int q = p;
        while(q <= r && preorder[i] != inorder[q]){
            q++;
        }
        int leftTreeSize = q-p;
        TreeNode left = myBuildTree(preorder,i+1,i+leftTreeSize,inorder,p,q-1);
        TreeNode right = myBuildTree(preorder,i+leftTreeSize+1,j,inorder,q+1,r);
        root.left = left;
        root.right = right;
        return root;
    }
复制代码

根据前序和后续遍历构造二叉树（889）

题目描述

返回与给定的前序和后序遍历匹配的任何二叉树。

pre 和 post 遍历中的值是不同的正整数。

示例 1：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
复制代码

提示：

1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, …, pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

思路分析

这道题和上面的题目非常类似，前面是前序遍历和中序遍历，这里我们是前序遍历和后续遍历，根据前序遍历的顺序和后序遍历的顺序找出我们的原始二叉树，首先我们需要知道前序遍历的特点，根节点是在数组的第一个位置，而后序遍历的话，根节点是在最后。我们可以分别为 pre 数组和 post 数组分别区分出左侧二叉树和右侧二叉树对应的索引。

然后取出根节点，左边的节点根据pre和post位置对应的索引，右侧也是如此。

代码展示

解法一：

public TreeNode constructFromPrePost(int[] pre, int[] post) {
        return myBuildTree(pre,0,pre.length - 1,post,0,post.length - 1);
    }

    private TreeNode myBuildTree(int[] pre,int i,int j,int[] post,int p,int r){
        if(i > j){
            return null;
        }
        TreeNode root = new TreeNode(pre[i]);
        if(i == j){
            return root;
        }
        int q = p;
        while(q < r-1 && post[q] != pre[i+1]){
            q++;
        }
        int leftTreeSize = q-p+1;

        TreeNode left = myBuildTree(pre,i+1,i+leftTreeSize,post,p,q);
        TreeNode right = myBuildTree(pre,i+leftTreeSize+1,j,post,q+1,r-1);
        root.left = left;
        root.right = right;
        return root;

    }
复制代码