刷刷刷 Day 18 | 106. 从中序与后序遍历序列构造二叉树

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

LeetCode题目要求

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

解题思路

想要通过中序和后序遍历序列的数组来构造二叉树，

1. 首先要找到 root 节点，通过后序遍历的数组的最后一个元素可以找到。
2. 当找到第一个节点后，由它来分隔中序遍历数组，这样也就可以找到中序数组的左右分隔数组，即为 root 节点的左右子树
3. 接着再根据第 2 步所分隔出的中序左右数组及下标索引分别得到 中序数组的左右数组索引，和后序数组的左右数组索引
4. 递归构造左右子树
5. 返回 root

上代码

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

    private TreeNode traversal(int[] inorder, int[] postorder, int inorderBegin, int inorderEnd, int postorderBegin, int postorderEnd) {
        if (postorderEnd == postorderBegin) {
            return null;
        }
        // 根据 postorder 找到 root 节点，数组最后一个元素
        int rootVal = postorder[postorderEnd - 1];

        // 构造 root 节点
        TreeNode root = new TreeNode(rootVal);
        if (postorderEnd - postorderBegin == 1) {
            return root;
        }

        // 定义分隔 inorder 的索引
        int cutPoint = 0;
        // 切割 inorder 数组，根据已知的 rootVal 进行分隔, 分为中序左数组和中序右数组
        for (int i = 0; i < inorder.length; i++) {
            if (rootVal == inorder[i]) {
                cutPoint = i;
                break;
            }
        }

        // 左中序, 左闭右开
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = cutPoint;
        // 右中序, 左闭右开
        int rightInorderBegin = cutPoint + 1;
        int rightInorderEnd = inorderEnd;

       // 左后序区间, 左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + cutPoint - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间, 左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (cutPoint - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了

        // 切割 postorer 数组，根据 inorder ，分为[]后序左数组和后序右数组
        root.left = traversal(inorder, postorder, leftInorderBegin, leftInorderEnd, leftPostorderBegin, leftPostorderEnd);
        root.right = traversal(inorder, postorder, rightInorderBegin, rightInorderEnd, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
}

重难点

找 root 节点，然后通过节点分隔中序数组，就找到了左右子树，然后再接着通过中序节点来分隔后序数组，通过递归完成操作
附：学习资料链接