题解 | #线段树编号问题#

思路

题目分析

1. 题目给出了build函数的规则，从根节点开始，递归地按照树的结构进行向下延伸，延伸出一个节点就进行编号。
2. 编号的规则：当前结点编号i时，左子节点编号为i*2，右子节点编号为i*2+1
3. 左右子树的划分规则是根据给定的区间进行二分向下取整划分，直到区间长度为0（结点中左右下标相同）为止停止划分。
4. 返回能够划分的最大的编号

• 我们可以暴力进行递归，直接递归地使用build函数，这样时间代价很大。
• 我们也可以有选择地按照二分的方法，选出一条可以产生出最大编号的路径。因此我们难点思路就在于如何选择左右子树方向，使得编号能够达到最大。
  • 我们可以总结发现，每次划分结果出来的左右子节点各自的区间长度，满足一种规律，即左区间长度与右区间长度相等，或者左区间长度比右区间长度大1
  • 如果经过一次划分后，左区间划分的长度为0，则说明已经到达叶子结点，则说明此次划分应该选择与这个左区间相邻的右区间，毕竟右区间的此次编号比左区间的此次编号大1
  • 当左区间划分长度非0时候，直观上我们认为如果此次划分的左区间长度>右区间长度，则向左子树继续递归是能够获得最大编号结点的，但是这存在一个问题
    • 对于案例[1,7]，划分出的左右子区间为[1,4],[5,7]，左区间长度>右区间长度。
    • 但是最终的划分情况是，左右子树的深度是一样的，因此在遇到上一条中所述情况时应该选择右区间才能获得最大的编号，直接以左区间长度>右区间长度判断要选择递归左子树方向的想法是错误的。
  • 因此我们可以发现规律，当左区间划分的长度=2的幂次时候，左子树的深度才会比右子树的深度大。
  • 这时才能选择左子树进行递归
  • 对于下图的[1,5]情况，最终的编号应该返回9

方法一：暴力方法（python实现，python超时，但同样的方法c++不超时）

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param T int整型 
# @param a int整型一维数组 
# @return int整型一维数组
#
class Solution:
    ans = 0
    mx = 0
    def wwork(self , T , a ):
        # write code here
        res = []
        for i in range(T):
            self.ans = 0             # 维护初始化的ans值
            self.mx = 0              # 维护类中成员变量mx来存储每一个n值对应的最大编号结果
            self.build(1, 1, a[i])
            res.append(self.mx)
        return res
    def build(self, x, y, z):        # 直接使用递归函数，其中x,y,z是题目定义的build函数参数
        self.ans = x                 # build函数代码是将题目要求进行代码语言化处理，可以理解为转述题干已知信息
        if(self.ans > self.mx):
            self.mx = self.ans
        if y == z:
            return
        mid = int((y+z)/2)
        self.build(x*2, y, mid)      # 进行左递归
        self.build(x*2+1,mid+1,z)    # 进行右递归

复杂度分析

• 时间复杂度：，对于列表a中的值，每进行一次ans计算的最差的代价认为为，共进行T次。
• 空间复杂度：，递归栈空间

方法二：二分法选择递归方向（python实现）

• 其实也是递归的一种剪枝方法，只不过我们没有用递归的形式。

class Solution:
    def wwork(self , T , a ):
        # write code here
        res = a
        for i in range(len(a)):
            z = a[i]
            x= 1
            y= 1
            while y!= z:
                mid = (z+y)//2       # 计算左右两边划分的点mid
                l = mid-y            # 计算左子区间的长度
                r = z - mid -1       # 计算右子区间的长度
                # 进入左子树的条件要同时满足3个，左子树的深度才更大
                # 左自区间更长，且左子区间不能为0，且左子区间的值为2的幂次
                if l>r and l != 0 and (l & (l-1) == 0):    #按照如上的三个判断进入if的分支
                    x = x*2
                    z = mid
                else:
                    x = x*2+1
                    y = mid+1
            res[i] = x
        return res 

复杂度分析

• 时间复杂度：，采用了二分方式优化了时间
• 空间复杂度：，使用了常数空间