lc108.将有序数组转换为二叉搜索树
说是转换为二叉搜索树，其实是平衡二叉搜索树。
代码一：转化为二叉搜索树
如果是普通二叉搜索树的话，如下代码就可以了
def sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: TreeNode"""root_val = nums[0]root = TreeNode(root_val)def init_BST(node, val):if not node:return TreeNode(val)if val < node.val:node.left = init_BST(node.left, val)else:node.right = init_BST(node.right, val)return nodefor i in range(1, len(nums)):init_BST(root, nums[i])return root
代码二：转换为平衡二叉搜索树
因为我们拿到的是一个有序数组，所以我们选取一个位置居中的数，递归分治左右两区间分别为左子树和右子树即可。
class Solution(object):def sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: TreeNode"""def traversal(left, right):# 定义左闭右闭if left>right:return Nonemid = (left+right)>>1mid_node = TreeNode(nums[mid])mid_node.left = traversal(left,mid-1)mid_node.right = traversal(mid+1, right)return mid_noderoot = traversal(0, len(nums)-1)return root
因为用了位运算加速，所以效率是35ms，击败90.83%。如果没有用位运算的话，大概是击败70%左右。
lc538. 把二叉搜索树转换为累加树
class Solution(object):def convertBST(self, root):""":type root: TreeNode:rtype: TreeNode"""def postorder(node, pre_val):if not node:return Nonepostorder(node.right, pre_val)node.val += pre_val[0]pre_val[0] = node.valpostorder(node.left, pre_val)return noderoot = postorder(root, [0])return root
效率：55ms，击败60.06%
