当前位置：首页 > article >正文

代码随想录刷题day52|（二叉树篇）106.从中序与后序遍历序列构造二叉树

article 2025/3/26 10:56:46

一、二叉树理论知识

二、构造二叉树思路

2.1 构造二叉树流程（给定中序+后序

2.2 整体步骤

2.3 递归思路

2.4 给定前序和后序

三、相关算法题目

四、易错点

一、二叉树理论知识

详见：代码随想录刷题day34|（二叉树篇）二叉树的递归遍历-CSDN博客

二、构造二叉树思路

2.1 构造二叉树流程（给定中序+后序

给定中序和后序的节点值构造唯一二叉树：

中序：左中右：9 3 15 20 7

后序：左右中：9 15 7 20 3

由后序可知：最后一个结点 3 一定为根节点 9 15 7 20 3

由中序可知：左子树为 9 右子树为 15 20 7 9 3 15 20 7

由后序可知：左子树的根节点为 9 （也只有唯一一个结点 9 ）右子树的根节点为 20

由中序可知：右子树的左节点为 15 右节点为 7

2.2 整体步骤

1.如果后序数组为空，则说明遍历结束；

2.后序数组最后一个元素为(根)结点元素；

3.在中序数组中寻找对应结点元素，作为切割点，分割左右子树；

4.切割中序数组，切成左右区间；

5.切割后序数组：根据中序数组中的左右区间，再去切割后序数组中的左右区间；

6.然后递归处理切割后的左区间和右区间；

2.3 递归思路

1.递归函数返回值和参数

返回构造好的根节点，参数：中序数组和后序数组；

2.终止条件

后序数组为空，返回为空，假设后序数组长度＝中序数组长度，不考虑其他异常情况；

3.单层递归逻辑

处理特殊情况：如果后序数组长度为1，则说明这棵树只有一个结点，即为根节点又为叶子节点；

首先获取后序数组中最后一个结点的值val；

遍历中序数组，找到val所在的下标位置index；

根据index切割中序数组，得到左中序数组、右中序数组；

根据左中序数组的大小和右中序数组的大小来切割后序数组，得到左后序数组、右后序数组；

根据左中序和左后序递归处理左子树，右中序和右后序递归处理结点的右子树；

切数组的时候注意区间的定义，左闭右开，左闭右闭

一定先切中序，分开左右，再去切后序，否则后序无法分开左右；

一定打日志来找问题？ debug？就是把每一步划分的数组打印出来看 printf

2.4 给定前序和后序

不可以

因为只能找出根节点，但是分不开左右区间，构造二叉树一定要有中序遍历的数组；

三、相关算法题目

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

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return backtracking(inorder,postorder);
    }
    private TreeNode backtracking(int[] inorder, int[] postorder){
        if(postorder.length == 0 || inorder.length == 0){
            return null;
        }
        TreeNode root = new TreeNode();
        root.val = postorder[postorder.length - 1];
        if(postorder.length == 1){
            return root;
        }
        int index = 0;
        for(int i = 0;i < inorder.length;i++){
            if(inorder[i] == postorder[postorder.length - 1]){
                index = i;
                break;
            }
        }
        //切割中序数组 得到左中序数组
        int[] leftInorder = Arrays.copyOfRange(inorder,0,index);
        //得到右中序数组
        int[] rightInorder = Arrays.copyOfRange(inorder,index + 1,inorder.length);
        //切割后序数组 得到左后序数组
        int[] leftPostorder = Arrays.copyOfRange(postorder,0,leftInorder.length);
        //得到右后序数组
        int[] rightPostorder = Arrays.copyOfRange(postorder,leftInorder.length,postorder.length - 1);
        //递归处理左子树 根据左中序和左后序
        root.left = backtracking(leftInorder,leftPostorder);
        //递归处理右子树 根据右中序和右后序
        root.right = backtracking(rightInorder,rightPostorder);
        return root;
    }
}