数据结构和算法【64】从中序和后序遍历序列构造二叉树

皮皮克克 2023-10-15

点击关注公众号，干货第一时间送达

屏幕前的你，

没有看错

今天还是一道通过遍历数组构造二叉树的题目，

和前面的两篇文章：

数据结构和算法【63】根据前序和后序遍历构造二叉树

数据结构和算法【62】从前序和中序遍历序列构造二叉树

互为三剑客。

掌握了这三道题目，

这类题型，就完全通晓了！

还是来自力扣：

原题链接：

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

一、屏幕前的吴彦祖和刘亦菲们，请听题

举个例子：

结合前面两篇文章：

数据结构和算法【63】根据前序和后序遍历构造二叉树

数据结构和算法【62】从前序和中序遍历序列构造二叉树

介绍的解题套路，

本题是不是手到擒来了！

二、解题

如上图，

可以直接看出，

中序遍历结果：inorder = [4, 2, 5, 1, 6, 3, 7]

后序遍历结果：postorder = [4, 5, 2, 6, 7, 3, 1]

代码过程：

1，后序遍历数组的最后一个元素肯定是根节点

这个位置的值，我们可以直接通过数组下标就能找到，

然后再找到这个值在中序遍历数组中的位置，

因为根据中序遍历的性质，根节点的左侧就是左子树的全部节点，

根节点的右侧就是右子树的全部节点：

2，同样的，后序遍历数组中，也可以通过中序数组可以确定的左右子树元素个数，找到后序数组中的左右子树范围：

3，然后呢，通过递归，进入到左右子树中，继续相同的步骤，进行划分，就能填充完整颗二叉树了

看看代码。

完整代码：

public class CodingDemo {

    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 从中序和后序遍历序列构造二叉树
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return process3(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);
    }
    
    private static HashMap<Integer, Integer> map = new HashMap<>();


    private static TreeNode process3(int[] inorder, int[] postorder, int iL, int iR, int pL, int pR){
        if (iL > iR || pL > pR){
            return null;
        }

        //后序数组的最后一个元素就是根节点
        TreeNode root = new TreeNode(postorder[pR]);

        //如果当前遍历只有一个元素，直接返回
        if (iL == iR){
            return root;
        }

        //找到根节点值，在中序遍历数组中的位置，用于划分左右子树
        int index = map.get(postorder[pR]);

        root.left = process3(inorder, postorder, iL, index-1, pL, pL+index-iL-1);
        root.right = process3(inorder, postorder, index+1, iR, pL+index-iL, pR-1);

        return root;
    }

}