669. 修剪二叉搜索树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
    3
  1    4
    2
 */
func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil {
        return nil
    }
    val := root.Val
    if low <= val && val <= high {
        root.Left = trimBST(root.Left, low, high)
        root.Right = trimBST(root.Right, low, high)
        return root
    } 
    if low > val {
        return trimBST(root.Right, low, high)
    } 
    if val > high {
        return trimBST(root.Left, low, high)
    }

    return root
}

108.将有序数组转换为二叉搜索树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func build(nums []int, l, r int) *TreeNode{
    if l > r {
        return nil
    }
    mid := (l + r) >> 1
    x := nums[mid]
    root := &TreeNode{Val: x}
    root.Left = build(nums, l, mid-1)
    root.Right = build(nums, mid+1, r)
    return root
}

func sortedArrayToBST(nums []int) *TreeNode {
    return build(nums, 0, len(nums)-1)
}

538.把二叉搜索树转换为累加树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var sum = 0
func inorderReverse(root *TreeNode) {
    if root == nil {
        return
    }
    inorderReverse(root.Right)
    sum += root.Val
    root.Val = sum
    inorderReverse(root.Left)
}
func convertBST(root *TreeNode) *TreeNode {
    sum = 0
    inorderReverse(root)
    return root
}

---

• 分类： 算法
• 标签： 算法基础 二叉树