从中序与后序遍历序列构造二叉树 Posted on 2021-06-22 00:00:00 2021-06-26 00:00:00 by Author 摘要 给你中序与后序遍历的结果，你能构造一颗二叉树吗？？？？？？？ # 从中序与后序遍历序列构造二叉树 1. 题目描述 - 根据一棵树的中序遍历与后序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。 2. 示例描述 - 示例一 - 输入： ``` 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] ``` - 输出： ``` 3 / \ 9 20 / \ 15 7 ``` - 示例二 - 输入： ``` 中序遍历 inorder = [2,1,3] 后序遍历 postorder = [2,3,1] ``` - 输出： ```java 1 / \ 2 3 ``` 3. 解题思路 - 这道题目说实话有点难度，因为给定一颗二叉树，让我们自己遍历操作，这比较简单，但是如果让我们自己构造二叉树，这就非常有难度了，因为我们既要看中序遍历的节点，又要看后序遍历的节点，之后找出一个确定的根节点，然后还要继续去寻找该左孩子在哪，右孩子在哪，然后就这样七倒八颠的，把整个人都整懵逼咯。 - 这里，我只是按照自己的想法来谈谈自己的理解，我只能知其意，但是让我具体表述清楚还是有点难度，我尽力把我理解的都表达出来。首先我们知道中序遍历的顺序是:`左中右`,后序遍历的顺序是：`左右中`,然后我们把他们遍历的顺序放在一起看看 他们的关系 >中序:`左中右` > >后序:`左右中` - 我们可以发现中序遍历和后序遍历中的`左孩子`与`右孩子`遍历的相对位置没有变(这里说的是相对位置),只是`父节点`的位置有变化，那么我们是不是可以根据中序遍历的特点，只要找到一个`父节点`，那么他的`左子树`与`右子树`的位置就确定了。因为找到`父节点`，在`父节点`的左侧就是左子树节点的集合，在`父节点`的右侧就是右子树节点的集合。接下来，怎么找到`父节点`尼，后序遍历给我们提供了一个条件，就是后序遍历最后一个节点，就是父节点，我们只用在中序遍历找到该节点的位置，就能找到父节点的位置(题目说了，每个节点的值是唯一的，这样就确保构造二叉树没有二义性)。之后该节点的左子树与右子树，在中序遍历中的位置就卡死了。又因为左子树与右子树位置卡死了，就能找到左子树与右子树节点的个数，从而就能在后序遍历中卡死该左子树与右子树后序遍历的位置。这样就完成了一个节点的构造，那么其他的节点构造与上面讲的原理都是一样的，所以这里用递归方式去解决，最后我们根据中序遍历和后序遍历的节点，构造完整棵树之后，那么整个流程就完事。 - 接下来就是怎么在中序遍历和后序遍历中卡左子树与右子树的位置尼。首先，我们晓得，在中序遍历中查找父节点，找出之后，该位置之前的所有节点都是左子树，那么我们根据该位置下标与起始坐标相减，就能得到该左子树的节点个数，从而后序遍历中，我们就能确定左子树遍历的位置了，就是在后序遍历的起始位置上加上该左子树节点的个数就好了,同理，右子树的算法也是一样的，就是在中序遍历中找到该节点的位置，该节点之后就是该节点的右子树结合，那么中序遍历的终止位置，减去改下标，就是右子树节点的个数，从而，在后序遍历中，就能找出该节点右子树的后序遍历的位置了，这里我们已经算出该节点左子树的节点个数，那么后序遍历的右子树节点的起始位置就是后序遍历的左子树节点的末尾位置，然后再到该位置加上右子树的节点个数，就是该节点下的右子树后序遍历的位置。这样我们就找到一个节点的值，同时左子树，右子树的中序与后序遍历的位置也找到了，那么继续去构造左子树，右子树中其他的节点，构造的方法与该节点构造的形式是一样的，所以用了递归方式去解决。 - 以上就是我个人的理解，我已经尽可能描述我的理解，有可能还是讲的不太清楚，不妨看看代码去理解吧，具体实现如下代码。 4. 代码示例 ```java public TreeNode buildTree(int[] inorder, int[] postorder) { //根据中序遍历与后序遍历构造一颗二叉树的方法 return constructTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); } //这里li,ri分别代表本次递归时中序遍历的开始位置与结束位置[都是闭区间],即inorder[li]和inorder[ri]有值，没有越界 //这里lp,rp分别代表本次递归时后序遍历的开始位置与结束位置[都是闭区间],即postorder[lp]和inorder[rp]有值，没有越界 public TreeNode constructTree(int[] inorder, int li, int ri, int[] postorder, int lp, int rp) { //如果中序遍历的开始位置小于结束位置，说明还有节点要构造，那么继续递归构造 if (lp <= rp) { //找出本次递归时该节点的位置 int i = 0; //从中序遍历中找出后序遍历中最后一个节点在中序遍历的位置 for (i = li; i <= ri; i++) { if (postorder[rp] == inorder[i]) { break; } } //找到之后，构造该节点 TreeNode node = new TreeNode(postorder[rp]); //然后继续构造该节点的左子树的其他节点 //因为是该节点的左子树，那么该中序遍历的起始位置要变化，同时后序遍历的起始位置也要变化 //从中序与后序遍历的特点看，中序遍历的左子树位置就是该节点(本次构造的节点)之前的节点(即为：li,到i-1)，因为是闭区间，所以i-1 //从后序遍历的特点看，后序遍历的左子树位置就是从开始位置到该节点的个与起始位置之和的位置(lp到lp+(i-li)-1) // (i-li)为左子树的个数,那么为什么要-1,因为是用的闭区间，所以减一。 node.left = constructTree(inorder, li, i - 1, postorder, lp, lp + (i - li - 1)); //然后继续构造该节点的右子树的其他节点 //因为是该节点的右子树，那么该中序遍历的起始位置要变化，同时后序遍历的起始位置也要变化 //从中序与后序遍历的特点看，中序遍历的右子树位置就是该节点(本次构造的节点)之后的节点(即为：i+1,到ri)，因为是闭区间，所以i+1 //从后序遍历的特点看，后序遍历的右子树位置就是从左子树结束的位置到右子树的个数加上左子树结束位置的和的位置(lp+(i-li)-1,rp-1) // (rp-1)从何而来，因为本次构造，只消耗了后序遍历的一个节点，而且是从后序遍历末尾消耗的，所以右子树结束的位置，我们直接用 rp-1即可 // 不用再去右子树结束的位置了 node.right = constructTree(inorder, i + 1, ri, postorder, lp + (i - li), rp - 1); //构造完成后返回该构造的节点即可 return node; } //如果中序遍历的开始位置大于结束位置，说明没有节点要构造了，返回null即可 return null; } ```
{{ item.content }}
{{ child.content }}