Golang题解-不创建树，只在递归中得到结果

分析题意可以知道取出每层的最右侧的值然后存放数组即可。

使用DLR可以取到每层的最左边的值，那么我们可以使用“DRL”取到每层最右边的值。也就是说每次先遍历右子树而不是左子树。

那么如何保证每层只取一个呢，思考每层具有自身独一无二的值：层深度。那么我们可以设置一个全局变量当前层深度和最大层深度，每层递归一开始当前深度+1，然后判断是否是最大深度，只有是最大深度才说明是第一次运行到本层，然后直接加入结果即可，然后本次递归结束后当前深度再-1。

具体代码可以参考“根据前序中序遍历结果得到二叉树”那道题。把先递归左改为先递归右，然后加上深度判断和并入结果即可。具体代码如下：

var res []int
var deep, maxDeep = 0, 0
 
func solve(xianxu []int, zhongxu []int) []int {
    help(xianxu, zhongxu)
    return res
}
 
func help(xianxu []int, zhongxu []int) {
    deep = deep + 1
    if deep > maxDeep {
        maxDeep = deep
        res = append(res, xianxu[0])
    }
    i := getIndex(zhongxu, xianxu[0])
 
    if i+1 < len(xianxu) {
        help(xianxu[i+1:], zhongxu[i+1:])
    }
    if i+1 > 1 {
        help(xianxu[1:i+1], zhongxu[:i])
    }
    deep = deep - 1
}
 
func getIndex(arr []int, val int) int {
    for i, r := range arr {
        if r == val {
            return i
        }
    }
    return -1
}