108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

簡單
給你一個整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列，請你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹。
高度平衡 二叉樹是一棵滿足「每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。

示例 1：
[圖片]
輸入：nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：
[圖片]

示例 2：
[圖片]
輸入：nums = [1,3]
輸出：[3,1]
解釋：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索樹。

提示：

• 1 <= nums.length <= 10(4)
• -10(4) <= nums[i] <= 10(4)
• nums 按 嚴(yán)格遞增 順序排列

代碼

package __tree/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func sortedArrayToBST(nums []int) *TreeNode {if len(nums) == 0 {return nil}//先序排列，根左右mid := len(nums) / 2x := nums[mid]root := &TreeNode{x, nil, nil}root.Left = sortedArrayToBST(nums[:mid])root.Right = sortedArrayToBST(nums[mid+1:])return root
}

538. 把二叉搜索樹轉(zhuǎn)換為累加樹

中等
給出二叉 搜索 樹的根節(jié)點，該樹的節(jié)點值各不相同，請你將其轉(zhuǎn)換為累加樹（Greater Sum Tree），使每個節(jié)點 node 的新值等于原樹中大于或等于 node.val 的值之和。
提醒一下，二叉搜索樹滿足下列約束條件：

• 節(jié)點的左子樹僅包含鍵 小于 節(jié)點鍵的節(jié)點。
• 節(jié)點的右子樹僅包含鍵 大于 節(jié)點鍵的節(jié)點。
• 左右子樹也必須是二叉搜索樹。
  注意：本題和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：
[圖片]
輸入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
輸出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
輸入：root = [0,null,1]
輸出：[1,null,1]
示例 3：
輸入：root = [1,0,2]
輸出：[3,3,2]
示例 4：
輸入：root = [3,2,4,1]
輸出：[7,9,4,10]

提示：

• 樹中的節(jié)點數(shù)介于 0 和 10(4)( )之間。
• 每個節(jié)點的值介于 -10(4) 和 10(4) 之間。
• 樹中的所有值 互不相同 。
• 給定的樹為二叉搜索樹。

代碼

package __tree/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
var pre intfunc convertBST(root *TreeNode) *TreeNode {pre = 0 //這一部很重要traversal(root)return root
}func traversal(cur *TreeNode) {if cur == nil {return}traversal(cur.Right)cur.Val += prepre = cur.Valtraversal(cur.Left)
}
func convertBST(root *TreeNode) *TreeNode {var sum inttraverse(root, &sum)return root
}func traverse(node *TreeNode, sum *int) {if node == nil {return}traverse(node.Right, sum)*sum += node.Valnode.Val = *sumtraverse(node.Left, sum)
}

669. 修剪二叉搜索樹

中等
給你二叉搜索樹的根節(jié)點 root ，同時給定最小邊界low 和最大邊界 high。通過修剪二叉搜索樹，使得所有節(jié)點的值在[low, high]中。修剪樹 不應(yīng)該 改變保留在樹中的元素的相對結(jié)構(gòu) (即，如果沒有被移除，原有的父代子代關(guān)系都應(yīng)當(dāng)保留)。 可以證明，存在 唯一的答案 。
所以結(jié)果應(yīng)當(dāng)返回修剪好的二叉搜索樹的新的根節(jié)點。注意，根節(jié)點可能會根據(jù)給定的邊界發(fā)生改變。

示例 1：
[圖片]
輸入：root = [1,0,2], low = 1, high = 2
輸出：[1,null,2]
示例 2：
[圖片]
輸入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
輸出：[3,2,null,1]

提示：

• 樹中節(jié)點數(shù)在范圍 [1, 10(4)] 內(nèi)
• 0 <= Node.val <= 10(4)
• 樹中每個節(jié)點的值都是 唯一 的
• 題目數(shù)據(jù)保證輸入是一棵有效的二叉搜索樹
• 0 <= low <= high <= 10(4)

代碼

package __tree/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func trimBST(root *TreeNode, low int, high int) *TreeNode {if root == nil {return nil}if root.Val < low {r := trimBST(root.Right, low, high)return r}if root.Val > high {l := trimBST(root.Left, low, high)return l}root.Left = trimBST(root.Left, low, high)root.Right = trimBST(root.Right, low, high)return root
}