LeetCode 0669.修剪二叉搜索树

修剪二叉搜索树

给你二叉搜索树的根节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

思路

修剪操作：

如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点
如果root（当前节点）的元素大于high的数值，那么应该递归左子树，并返回左子树符合条件的头结点
接下来要将下一层处理完右子树的结果赋给root->left，处理完左子树的结果赋给root->right，最后返回root节点

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val < low { //如果该节点值小于最小值，则该节点更换为该节点的右节点值，继续遍历
        right := trimBST(root.Right, low, high)
        return right //返回该节点的右子树
    }
    if root.Val > high { //如果该节点的值大于最大值，则该节点更换为该节点的左节点值，继续遍历
        left := trimBST(root.Left, low, high)
        return left
    }
    root.Left = trimBST(root.Left, low, high)   // 把下一层返回的的孩子接住
    root.Right = trimBST(root.Right, low, high) // 把下一层返回的的孩子接住
    return root
}

Link

GitHub