Max Tree(最大树问题)
问题描述
给出一个没有重复的整数数组,在此数组上建立最大树的定义如下:
根是数组中最大的数
左子树和右子树元素分别是被父节点元素切分开的子数组中的最大值
利用给定的数组构造最大树。
样例
给出数组 [2, 5, 6, 0, 3, 1],构造的最大树如下:
6
/ \
5 3
/ / \
2 0 1
根据九章课程的思维想了半天也没想出来正确的实现,简单来说思路就是由下自上的根据数组遍历逐步构建树,然后通过一个栈来维护整个栈的单调递减性,如果当前值大于栈顶值则将栈顶结点弹出安装在当前值的左孩子下,(这道题逻辑太神奇了... 暂时还没看懂)