定义二叉树节点如下:
class Node {
public int value;
public Node left;
public Node right;

public Node(int data) {
this.value = data;
}
}

一个数组的MaxTree定义如下:
1,数组必须没有重复元素;
2,MaxTree是一棵二叉树,数组的每一个值对应一个二叉树节点;
3,包括MaxTree树在内并且在其中的每一颗子树上,值最大的节点都是树的头;

给定一个没有重复元素的数组arr,写出生成这个数组的MaxTree的函数,要求如果数组长度为N,时间复杂度O(N),额外空间复杂度O(N)

 

解答:

难度:校
举个例子来说明如何在满足时间空间复杂度的要求下,生成MaxTree。
arr = {3, 4, 5, 1, 2}
3的左边第一个比3大的数:无,3的右边第一个比3大的数:4
4的左边第一个比4大的数:无,4的右边第一个比4大的数:5
5的左边第一个比5大的数:无,5的右边第一个比5大的数:无
1的左边第一个比1大的数:5,1的右边第一个比1大的数:2
2的左边第一个比2大的数:5,2的右边第一个比2大的数:无

以下列原则建立这棵树:
1,每一个数的父节点是它左边第一个比它大的数和它右边第一个比它大的数中,较小的那个;
2,如果一个数左边没有比它大的数,右边也没有,也就是说这个数是整个数组的最大值,那么这个数是MaxTree的头节点;

那么3, 4, 5, 1, 2的MaxTree为:

                             ___5___
                            /               \
                      __4            __2
                     /                 /
                    3               1
为什么通过这个方法能够正确的生成MaxTree呢?我们需要给出证明,证明分为两步:
1,通过这个方法,所有的数能生成一棵树,这棵树可能不是二叉树,但肯定是一棵树而不是多棵树(森林)。
我们知道,在数组中所有数都不同,而一个较小的数肯定会以一个比自己大的数作为父节点,
那么最终所有的数向上找都会找到数组中的最大值,所以它们会有一个共同的头。证明完毕。

2,通过这个方法,所有的数都最多只有两个孩子,也就是说这棵树可以用二叉树表示,而不需要多叉树。
要想证明这个问题,只需证明任何一个数在单独一侧,孩子数量都不可能超过1个。
假设a这个数在单独一侧有2个孩子,不妨设在右侧。
假设这两个孩子一个是k1,一个是k2
…a…k1…k2…
因为a是k1和k2的父,所以a>k1,a>k2;
根据题意,k1和k2不相等,所以k1和k2可以分出大小,先假设k1是较小的,k2是较大的:
那么k1可能会以k2为父节点,而绝对不会以a为父节点,因为根据我们的方法,每一个数的父节点是它左边第一个比它大的数和它右边第一个比它大的数中较小的那个,又有a>k2。
再假设k2是较小的,k1是较大的:
那么k2可能会以k1为父节点,也绝对不会以a为父节点,因为根据我们的方法,k1才可能是k2左边第一个遇到的比k2大的数,而绝对不会轮到a;
总之,k1和k2肯定有一个不是a的孩子。
所以,任何一个数的单独一侧,孩子数量都不可能超过2个,最多会有一个。进而我们知道,任何一个数最多会有2个孩子,而不会更多。
证明完毕。

以上证明了该方法是有效的,那么如何尽可能快的找到每一个数左右两边第一个比它大的数呢?利用栈。
找每个数左边第一个比它大的数,从左到右遍历每个数,栈中保持递减序列,新来的数不停的Pop出栈顶直到栈顶比新数大或没有数。
以[3,1,2]为例,首先3入栈,接下来1比3小,无需pop出3,1入栈,并且确定了1往左第一个比他大的数为3。接下来2比1大,1出栈,2比3小,2入栈。并且确定了2往左第一个比他大的数为3。
用同样的方法可以求得每个数往右第一个比他大的数。
具体请参看如下代码中的getMaxTree方法。

 

欢迎留言