代码随想录算法训练营第二十天 | 669、108、538

算法
, , ,

669. 修剪二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package main

/**
 * 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
    }
    // 当前节点值小于 low，左子树全舍去，处理右子树
    if root.Val < low {
        return trimBST(root.Right, low, high)
    }
    // 当前节点值大于 high，右子树全舍去，处理左子树
    if root.Val > high {
        return trimBST(root.Left, low, high)
    }
    // 当前节点在范围内，递归处理左右子树
    root.Left = trimBST(root.Left, low, high)
    root.Right = trimBST(root.Right, low, high)
    return root
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    return helper(nums, 0, len(nums)-1)
}

func helper(nums []int, start, end int) *TreeNode {
    if start > end {
        return nil
    }
    mid := (start + end) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = helper(nums, start, mid-1)
    root.Right = helper(nums, mid+1, end)
    return root
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    sum := 0
    var helper func(*TreeNode)
    helper = func(node *TreeNode) {
        if node == nil {
            return
        }
        helper(node.Right) // 先递归处理右子树
        sum += node.Val    // 累加当前节点值
        node.Val = sum     // 更新当前节点值为累加和
        helper(node.Left)  // 再递归处理左子树
    }
    helper(root)
    return root
}