今日学习
将有序数组转换为平衡搜索二叉树
视频讲解：https://www.bilibili.com/video/BV1uR4y1X7qL
第一想法
既然是平衡的，那么必然是找mid，用递归秒了，注意结束的位置，当left>right
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function (nums) {
const buildtree = function (nums, left, right) {
if (left > right) return null
let mid = Math.floor(left + (right - left) / 2)
let root = new TreeNode(nums[mid])
root.left = buildtree(nums, left, mid - 1)
root.right = buildtree(nums, mid + 1, right)
return root
}
return buildtree(nums, 0, nums.length - 1)
};
把二叉树转换为累加树
视频讲解：https://www.bilibili.com/video/BV1d44y1f7wP
第一想法
注意读题，要从最右侧开始向左加，运用递归，中序遍历改变当前节点的val，
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var convertBST = function (root) {
let pre = 0
const leijia = function (cur) {
if (cur) {
leijia(cur.right)
cur.val += pre
pre = cur.val
leijia(cur.left)
}
return cur
}
return leijia(root)
};
