使用两种遍历结果构造二叉树

发表于 更新于 分类于 ， 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟
如何使用先序（后序）遍历和中序遍历来构造一棵二叉树？本篇文章将会以易懂的思路来解决这个问题

最近刷Leetcode时，遇到了一道题，给你一个二叉树的后序遍历和中序遍历的输入序列，如何把这棵树的结构构造出来？

下面贴出这道题的原地址从中序与后续遍历序列构造二叉树。

后序遍历和中序遍历的特点

不管是先序、中序、后序，它们的不同点在于访问根节点的时机，先序先访问根节点、后序最后访问根节点。

来看看原题给的样例。

1
2
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

来观察一下，可以发现中序遍历的一个特征：在中序遍历的序列中，根节点左边是左子树，根节点右边是右子树。中序遍历序列从前往后看的规律是：左子树->根节点->右子树。

也可以发现后序遍历的一个特征：左子树的叶子节点最先找到，右子树的叶子节点次之，根节点最后找到。比如后序遍历最后一个元素为3，再看看后序遍历倒数第二个元素20，它是根节点3的右子树，20再往前的元素7则是20的右子树，那么后序遍历的规律很明朗了，从遍历序列后往前看，根节点->右子树->左子树。

这个遍历的性质很重要，如此一来就可以通过分治算法来将遍历结果转换为二叉树。

分而治之

根据上面二叉树的性质，可以先通过后序遍历的最后一个元素找到根节点3，然后去中序遍历中找到根节点3，找到以后就可以将3左边的元素判定为左子树，3右边的元素判定为右子树。

1

然后先递归地对右子树进行处理（因为我们看后序遍历是从后面往前看的），再递归地对左子树进行处理，得到地就是完整地二叉树。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    int[] inorder,postorder;
	int postIndex;//记录后序遍历当前位置
    
    //在中序遍历中l和r下标之间寻找tar这个元素
	public int findIndexForNum(int tar,int l,int r) {
		for(int i=l;i<=r;i++) {
			if(inorder[i]==tar) {
				return i;
			}
		}
		return -1;
	}
    
    //建树的递归函数,l和r是当前子树在中序遍历中的范围
	public TreeNode build(int l,int r) {
		if(l>r) {
			return null;
		}
		int midVal=postorder[postIndex--];//从后序遍历中拿一个根节点
		TreeNode root=new TreeNode(midVal);
		int midIndex=findIndexForNum(midVal,l,r);
		root.right=build(midIndex+1,r);//先建右子树
		root.left=build(l,midIndex-1);
		return root;
	}
    
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		this.inorder=inorder;
		this.postorder=postorder;
		postIndex=postorder.length-1;
		return build(0,postIndex);
    }
}

用中序和先序遍历构造二叉树

其实道理也是一样的，只不过变成了从前往后遍历先序序列，具体做法仍然是分治+递归建树。