「力扣」第 106 题：从中序与后序遍历序列构造二叉树
- 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
- 我写的题解地址：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/hou-xu-bian-li-python-dai-ma-java-dai-ma-by-liwe-2/
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]返回如下的二叉树：
3 / \ 9 20 / \ 15 7
来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# https://www.bilibili.com/video/av7420546?from=search&seid=6242384381313003008
# 前序遍历的第 1 个点肯定是根结点
# 参考资料：https://articles.leetcode.com/construct-binary-tree-from-inorder-and-preorder-postorder-traversal/LeetCode 第 106 题：
二叉树相关的很多问题的解决思路都有分治法的思想在里面。
我们再复习一下分治法的思想：把原问题拆解成若干个与原问题结构相同但规模更小的子问题，待子问题解决以后，原问题就得以解决，“归并排序” 和 “快速排序” 都是分治法思想的应用，其中 “归并排序” 先无脑地“分”，在 “合” 的时候就麻烦一些；“快速排序” 开始在 partition 上花了很多时间，即在 “分” 上使了很多劲，然后就递归处理下去就好了，没有在 “合” 上再花时间。
以题目中给出的例子为例，讲解如何构建二叉树。
中序遍历
inorder = [9,3,15,20,7]
后序遍历postorder = [9,15,7,20,3]
图画完以后才发现这个例子不太好，数组长度多一些就能把思路展现得更清楚了，各位客官老爷将就看一下啦。或者可以看一下我写的 「力扣」第 105 题 的 题解 ，两道问题的解法是一样的。
注意：这道问题其实并不难，我们在草稿纸上写写画画，就能把思路想清楚，但是在编码上会有一些小陷阱，在计算索引边界值要认真一些。
下面给出两种写法，区别在于空间复杂度：
方法一：在递归方法中，传入数组的拷贝
该方法在计算索引的时候会稍微容易一些。
Python 代码：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def buildTree(self, inorder, postorder):
assert len(inorder) == len(postorder)
if len(inorder) == 0:
return None
if len(inorder) == 1:
# 这里要返回结点，而不是返回具体的数
return TreeNode(inorder[0])
# 后序遍历的最后一个结点就是根结点
root = TreeNode(postorder[-1])
# 在中序遍历中找到根结点的索引，得到左右子树的一个划分
pos = inorder.index(postorder[-1])
# 这里的列表切片使用的是复制值，使用了一些空间，因此空间复杂度是 O(N)
root.left = self.buildTree(inorder[:pos], postorder[:pos])
root.right = self.buildTree(inorder[pos + 1:], postorder[pos:-1])Java 代码：
import java.util.Arrays;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
/**
* @param inorder 中序遍历序列
* @param postorder 后序遍历序列
* @return
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
int inlen = inorder.length;
int postlen = postorder.length;
assert inlen == postlen;
if (inlen == 0) {
return null;
}
if (inlen == 1) {
return new TreeNode(inorder[0]);
}
// 后序遍历的最后一个结点就是根结点
int rootVal = postorder[postlen - 1];
// 在中序遍历中找到根结点的索引，得到左右子树的一个划分
int dividePoint = 0;
for (int i = 0; i < inlen; i++) {
if (inorder[i] == rootVal) {
dividePoint = i;
break;
}
}
TreeNode rootNode = new TreeNode(rootVal);
// Arrays.copyOfRange() 方法的第 1 个参数是源数组
// 第 2 个参数是源数组的起始位置（可以取到）
// 第 3 个参数是源数组的起始位置（不可以取到）
// 这里复制了数组，使用了一些空间，因此空间复杂度是 O(N)
rootNode.left = buildTree(Arrays.copyOfRange(inorder, 0, dividePoint), Arrays.copyOfRange(postorder, 0, dividePoint));
rootNode.right = buildTree(Arrays.copyOfRange(inorder, dividePoint + 1, inlen), Arrays.copyOfRange(postorder, dividePoint, postlen - 1));
return rootNode;
}
}复杂度分析：
- 时间复杂度：$O(N)$，这里 $N$ 是二叉树的结点个数。
- 空间复杂度：$O(N)$。
方法二：在递归方法中，传入子数组的边界索引
注意：在递归方法中，有一个数组的边界索引，得通过计算得到，计算的依据是递归方法传入的“中序遍历数组”（的子数组）和“后序遍历数组”（的子数组）的长度是一样的。我的办法是解方程计算未知数，哈哈，傻呼呼的。具体需要计算哪个参数我在下面的代码中已经注明了。
Python 代码：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.inorder = None
self.postorder = None
def buildTree(self, inorder, postorder):
assert len(inorder) == len(postorder)
size = len(inorder)
self.inorder = inorder
self.postorder = postorder
return self.__dfs(0, size - 1, 0, size - 1)
def __dfs(self, in_l, in_r, post_l, post_r):
if in_l > in_r or post_l > post_r:
return None
val = self.postorder[post_r]
# 后序遍历的最后一个结点就是根结点
root = TreeNode(val)
# 在中序遍历中找到根结点的索引，得到左右子树的一个划分
pos = self.inorder.index(val)
# 注意：第 4 个参数是计算出来的，依据：两边区间长度相等
root.left = self.__dfs(in_l, pos - 1, post_l, pos - 1 - in_l + post_l)
# 注意：第 3 个参数是计算出来的，依据：两边区间长度相等
root.right = self.__dfs(pos + 1, in_r, post_r - in_r + pos, post_r - 1)
return rootJava 代码：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
private int[] inorder;
private int[] postorder;
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.inorder = inorder;
this.postorder = postorder;
int len = inorder.length;
return dfs(0, len - 1, 0, len - 1);
}
private TreeNode dfs(int inl, int inr, int postl, int postr) {
if (inl > inr || postl > postr) {
return null;
}
int val = postorder[postr];
int k = 0;
for (int i = inl; i < inr + 1; i++) {
if (inorder[i] == val) {
k = i;
break;
}
}
TreeNode root = new TreeNode(val);
// 注意：第 4 个参数是计算出来的，依据：两边区间长度相等
root.left = dfs(inl, k - 1, postl, k - 1 - inl + postl);
// 注意：第 3 个参数是计算出来的，依据：两边区间长度相等
root.right = dfs(k + 1, inr, postr + k - inr, postr - 1);
return root;
}
public static void main(String[] args) {
int[] inorder = {1, 3, 2};
int[] postorder = {3, 2, 1};
Solution solution = new Solution();
TreeNode res = solution.buildTree(inorder, postorder);
System.out.println(res);
}
}复杂度分析：
- 时间复杂度：$O(N)$，这里 $N$ 是二叉树的结点个数。
- 空间复杂度：$O(1)$。
题目描述（中等难度）
我写的题解地址：
根据二叉树的中序遍历和后序遍历还原二叉树。
思路分析
可以先看一下 105 题，直接在 105 题的基础上改了，大家也可以先根据 105 题改一改。
105 题给的是先序遍历和中序遍历，这里把先序遍历换成了后序遍历。
区别在于先序遍历的顺序是 根节点 -> 左子树 -> 右子树。
后序遍历的顺序是 左子树 -> 右子树 -> 根节点。
我们当然还是先确定根节点，然后在中序遍历中找根节点的位置，然后分出左子树和右子树。
对于之前的解法一，传数组的两个边界，影响不大，只要重新计算边界就可以了。
但是对于另外两种解法，利用 stop 和栈的算法，之前都是通过遍历前序遍历的数组实现的。所以构造过程是根节点，左子树，右子树。
但这里如果是后序遍历，我们先找根节点，所以相当于从右往左遍历，这样的顺序的话就成了，根节点 -> 右子树 -> 左子树，所以我们会先生成右子树，再生成左子树。
解法一
常规解法，利用递归，传递左子树和右子树的数组范围即可。
public TreeNode buildTree(int[] inorder, int[] postorder) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return buildTreeHelper(inorder, 0, inorder.length, postorder, 0, postorder.length, map);
}
private TreeNode buildTreeHelper(int[] inorder, int i_start, int i_end, int[] postorder, int p_start, int p_end,
HashMap<Integer, Integer> map) {
if (p_start == p_end) {
return null;
}
int root_val = postorder[p_end - 1];
TreeNode root = new TreeNode(root_val);
int i_root_index = map.get(root_val);
int leftNum = i_root_index - i_start;
root.left = buildTreeHelper(inorder, i_start, i_root_index, postorder, p_start, p_start + leftNum, map);
root.right = buildTreeHelper(inorder, i_root_index + 1, i_end, postorder, p_start + leftNum, p_end - 1,
map);
return root;
}解法二 stop 值
这里的话，之前说了，递归的话得先构造右子树再构造左子树，此外各种指针，也应该从末尾向零走。
视线从右往左看。
3
/ \
9 20
/ \
15 7
s 初始化一个树中所有的数字都不会相等的数，所以代码中用了一个 long 来表示
<------------------
中序
9, 3, 15, 20, 7
^ ^
s i
后序
9, 15, 7, 20, 3
^
p
<-------------------p 和 i 都从右往左进行遍历，所以 p 开始产生的每次都是右子树的根节点。之前代码里的++要相应的改成--。
int post;
int in;
public TreeNode buildTree(int[] inorder, int[] postorder) {
post = postorder.length - 1;
in = inorder.length - 1;
return buildTreeHelper(inorder, postorder, (long) Integer.MIN_VALUE - 1);
}
private TreeNode buildTreeHelper(int[] inorder, int[] postorder, long stop) {
if (post == -1) {
return null;
}
if (inorder[in] == stop) {
in--;
return null;
}
int root_val = postorder[post--];
TreeNode root = new TreeNode(root_val);
root.right = buildTreeHelper(inorder, postorder, root_val);
root.left = buildTreeHelper(inorder, postorder, stop);
return root;
}解法三 栈
之前解法是构造左子树、左子树、左子树，出现相等，构造一颗右子树。这里相应的要改成构造右子树、右子树、右子树，出现相等，构造一颗左子树。和解法二一样，两个指针的话也是从末尾到头部进行。
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder.length == 0) {
return null;
}
Stack<TreeNode> roots = new Stack<TreeNode>();
int post = postorder.length - 1;
int in = inorder.length - 1;
TreeNode curRoot = new TreeNode(postorder[post]);
TreeNode root = curRoot;
roots.push(curRoot);
post--;
while (post >= 0) {
if (curRoot.val == inorder[in]) {
while (!roots.isEmpty() && roots.peek().val == inorder[in]) {
curRoot = roots.peek();
roots.pop();
in--;
}
curRoot.left = new TreeNode(postorder[post]);
curRoot = curRoot.left;
roots.push(curRoot);
post--;
} else {
curRoot.right = new TreeNode(postorder[post]);
curRoot = curRoot.right;
roots.push(curRoot);
post--;
}
}
return root;
}总
理解了 105 题 的话，这道题很快就出来了，完全是 105 题的逆向思考。
