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

目录

一、二叉树理论知识

二、构造二叉树思路

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切割中序数组，得到左中序数组、右中序数组；

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

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

最后返回根节点；

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

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;}
}

四、易错点

1.判断后序数组和中序数组长度是否为0，要放在递归函数中，否则当左子树为空时，递归到下一层，即根结点的左子树时，后序数组已为空，长度为0，但此时不进行长度为0的校验，那么通过 后序数组的长度-1 来获取根节点的值 就会报错：

ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 0

2.获取左中序、右中序、左后序、右后序数组时，起始索引和终止索引要注意，起始索引包括，中止索引不包括，右后序中，终止索引要考虑去掉后序数组中的最后一个结点（根节点），即 postorder.length - 1；

3.优化建议：

• 可以用 HashMap 预处理 inorder 的值到索引的映射，避免每次递归都遍历查找 index。

• 可以用索引范围代替数组拷贝，减少空间开销（传递 inorder 和 postorder 的起始和结束索引，而不是拷贝数组）。

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

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

待续。。。。