【强基计划】LeetCode—根据二叉树的前、中序/中、后序构造二叉树

✨哈喽，进来的小伙伴们，你们好耶！✨

🍅🍅系列专栏:【强基计划】

✈️✈️本篇内容: 根据二叉树的前、中序/中、后序构造二叉树！

⛵⛵作者简介：一名双非本科大三在读的科班Java编程小白，道阻且长，你我同行！

🍱🍱码云存放仓库gitee：Java数据结构全部代码存放！

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解题思路：

本题要求我们根据前序遍历和中序遍历来构建这颗二叉树，那么思路非常简单。

1、由前序遍历的第一个节点就是根节点root，首先就得到了根节点。

2、那么得到了根节点，我们就去中序遍历的结果里面找到这个根节点，那么这个root的两侧就是我们的左子树和右子树。

3、定义一个i下标遍历前序的结果，那么这个新的节点就是新的左/右子树的根节点，然后在去中序遍历的结果中找到这个新的根节点，同理，它的两侧就是对应的左/右子树。(递归的思想)

代码实现：

/**
 * 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 preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
        //1、当前根节点是不是还有左子树 或者  右子树 
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        //2. 找到root再中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;
        if(rootIndex == -1) {
            return null;
        }
        //3、构建左子树和右子树 
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }

    private int findIndex (int[] inorder,int inbegin,int inend,int val) {
        for(int i = inbegin;i <= inend;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -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 postIndex = 0;

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        postIndex = postorder.length-1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }

    private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {
        //1、当前根节点是不是还有左子树 或者  右子树
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        //2. 找到root再中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
        postIndex--;
        if(rootIndex == -1) {
            return null;
        }
        //3、构建左子树和右子树

        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);

        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);

        return root;
    }

    private int findIndex (int[] inorder,int inbegin,int inend,int val) {
        for(int i = inbegin;i <= inend;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
        }
    }

运行结果：