BST reconstruction

简介

　　根据给定一个二叉树的遍历顺序来构造二叉树是一个经常讨论的问题。这里针对BST，也就是二叉搜索树的一些遍历顺序来构造对应二叉树的场景进行讨论。因为是二叉搜索树，它本身的一些特殊特性使得我们来处理它们的时候有些不同。在之前的文章里有针对二叉树的各种遍历实现进行过讨论，可以作为一并的参考。

 

问题分析

　　我们对二叉树的遍历最常用的有如下三种情况，前序、中序和后序遍历。每一种情况对应着我们访问元素的策略的不同，因此它们访问的序列也不同。从本身的定义来说，它们的访问更多的是一种递归的形式。针对二叉搜索树来说，它有一个独特的特性，就是每个节点的值比它的左子树的所有节点值大，同时比它右子树的所有节点小。也就是因为有这个特性，我们才可以根据一些遍历的顺序来重新构造整棵树。

　　现在，有几个问题值得我们讨论。是不是所有这几种遍历的序列都可以重新构造出它原来对应的二叉树来呢？如果可以，该怎么来构造？

　　首先假设我们有如下定义的树节点：

 

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

 

根据前序构造BST

　　我们都知道，对于二叉树的前序遍历来说，首先遍历的是它的根节点，然后是递归的遍历该节点的左子树，再递归的遍历该节点的右子树。所以对于一个序列来说，它的第一个元素肯定就是这棵树的根。按照原来的定义，我们需要找这个根的左右子节点。

　　在这里我们就需要利用到二叉搜索树的特性了。对于它来说，它的根节点的值是肯定大于左子树的，同样也是小于右子树的。所以对于根节点来说，要在后面的序列中找到它的左子节点，就需要去找比本身小的元素。而且根据定义，遍历完这个节点后就需要遍历访问它的左子节点。所以原则上就是该节点后米的那个元素。所以我们只需要判断它后面的那个节点是否小于该节点，如果是则表示找到了目标节点。否则说明这个节点的左子节点不存在。针对这种情况我们需要特殊处理。既然这个值不存在，我们期望的结果就是让原来根节点的左子节点为null。我们可以返回一个特定的值，让程序根据这个值来返回null。

　　对于右子节点的查找和推导也类似。我们去查找根节点后面第一个比它大的值。这也是根据前序遍历的定义推导。因为对该节点以及它的左子树遍历完之后才遍历它的右子树。而它和它左子树的节点元素值都小于等于它本身的值。所以只有当碰到比它大的时候才说明访问到它的右子树了。和查找左子节点类似，在没有找到的情况下返回特殊值-1。在程序处理时根据这个值返回null。

　　我们将上述的讨论定义成一个递归的过程，于是可以得到如下的实现代码：

 

public TreeNode reconstruct(int[] a) {
		if(a == null || a.length < 1) return null;
		return reconstructRec(a, 0, a.length - 1);
	}

	public TreeNode reconstructRec(int[] a, int cur, int end) {
		if(cur == -1 || cur > end) return null;
		TreeNode node = new TreeNode(a[cur]);
		int left = findL(a, cur);
		int right = findR(a, cur);
		node.left = reconstructRec(a, left, right - 1);
		node.right = reconstructRec(a, right, end);
		return node;
	}

	private int findL(int[] a, int cur) {
		if(cur + 1 < a.length && a[cur] > a[cur + 1]) return cur + 1;
		else return -1;
	}

	private int findR(int[] a, int cur) {
		for(int i = cur + 1; i < a.length; i++) {
			if(a[i] > a[cur]) return i;
		}

		return -1;
	}

 

根据中序构造BST

　　对于BST来说，对它的中序遍历则形成一个排序后的序列。但是根据这个排序的序列却不能唯一的确定对应的BST。假定以序列{1, 2, 3}来说，生成它的BST就可能有如下几种情况：

 　　而对于前面根据前序递归构造BST的问题来说，它可以首先确定根节点。然后在确定根节点的情况下根据本身的值范围特性缩小范围来递归的确定它的子节点。对于中序遍历来说则无法确定唯一的根节点。所以仅仅根据中序遍历的序列并不能唯一的构造BST。

 

根据后序构造BST

　　有了前面前序遍历的构造推导，后序遍历的推导也类似。根据它本身的定义， 最后访问到的元素是根节点，所以序列中最后的节点就是根节点。在确定了根节点的情况下，它的左子节点则应该在序列的前面，而且从定义来说应该是从该节点向前碰到的第一个小于它的元素。而求右子节点也类似，就看根节点的前一个元素是否为比它大的元素，是的则为它的右子节点，否则右子节点为空。

　　按照这样的思路，我们可以得到如下的代码实现：

 

public TreeNode reconstructByPostOrder(int[] a) {
		if(a == null || a.length < 1) return null;
		return reconstructByPostOrderRec(a, 0, a.length - 1);
	}

	public TreeNode reconstructByPostOrderRec(int[] a, int l, int cur) {
		if(cur == -1 || cur < l) return null;
		TreeNode node = new TreeNode(a[cur]);
		int left = findLeft(a, cur);
		int right = findRight(a, cur);
		node.left = reconstructByPostOrderRec(a, l, left);
		node.right = reconstructByPostOrderRec(a, left + 1, right);
		return node;
	}

	private int findLeft(int[] a, int cur) {
		for(int i = cur - 1; i >= 0; i--) {
			if(a[i] < a[cur]) return i;
		}

		return -1;
	}

	private int findRight(int[] a, int cur) {
		if(cur - 1 >= 0 && a[cur - 1] > a[cur]) return cur - 1;
		else return -1;
	}

 

根据层次遍历顺序构造BST

　　还有一个比较有意思的问题就是按层次的顺序遍历二叉树。因为是对应一层层的从左到右遍历二叉树。很明显，第一个节点就是根节点。而对于它的左子节点来说，肯定就是在后续的序列里碰到的比它小的元素。但是仅仅这个是否就足够了呢？假定对于某个子树来说，它当前的节点可能是某个节点的右子节点，这就表明这棵树的所有节点的值肯定会大于某个值了。所以不能仅仅根据一个值来判断节点的选择，需要取这个范围内的最小和最大值两个来确定。

　　另外，对于满二叉树来说，它的左右子节点的取值其实是在某个范围的。为了提高程序的查找速度，我们可以用这个左右子节点的值作为限定。这样在后续的查询中可以不用去遍历完整个数组。在实际的示例中，我们还可能有部分节点的左右子节点为空的情况。所以对它们的左右子节点的查找最大也就是我们所计算的那个值了。这个值的计算和前面堆排序里计算左右子节点的方法是一样的，可以看后面详细的代码实现。

　　这样，我们可以得到如下的实现代码：

 

public TreeNode reconstructByLevelOrder(int[] a) {
		if(a == null || a.length < 1) return null;
		return reconstructByLevelOrderRec(a, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	public TreeNode reconstructByLevelOrderRec(int[] a, int cur, int min, int max) {
		if(cur == -1) return null;
		TreeNode node = new TreeNode(a[cur]);
		int left = leftSon(a, min, cur);
		int right = rightSon(a, cur, max);
		node.left = reconstructByLevelOrderRec(a, left, min, a[cur]);
		node.right = reconstructByLevelOrderRec(a, right, a[cur], max);
		return node;
	}

	private int leftSon(int[] a, int min, int cur) {
		int left = cur * 2 + 1;
		int len = Math.min(a.length - 1, left);
		for(int i = cur + 1; i <= len; i++) {
			if(a[i] > min && a[i] < a[cur]) return i;
		}
		return -1;
	}

	private int rightSon(int[] a, int cur, int max) {
		int right = cur * 2 + 2;
		int len = Math.min(a.length - 1, right);
		for(int i = cur + 1; i <= len; i++) {
			if(a[i] > a[cur] && a[i] < max) return i;
		}
		return -1;
	}

 

总结

　　因为有了BST的值范围限定特性，我们才能够根据仅仅某些单个的遍历序列唯一的确定一棵树。上面的实现讨论里主要应用了递归的方式。在实际的实现中我们也可以采用一些非递归的方式。可以参照后面的参考材料。这里就不再赘述了。

 

参考材料

http://algs4.cs.princeton.edu/32bst/

http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-recursion/

http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-stack-without-recursion/