669.trim-a-binary-search-tree.md

669. Trim a Binary Search Tree

Clarification Questions

• Is the answer unique?
• Is low and high valid? (low <= high)

Test Cases

Normal Cases

Input: 
        5
      /   \
     3     7   
    / \   / \
   2   4 6   8
low = 3
high = 7
Output: 
        5
      /   \
     3     7
      \   /
       4 6

Edge / Corner Cases

• The root will be trimmed.

Input: 
        1
      /   \
     0     2
low = 2
high = 3
Output: 
        2

Input: 
        5
      /   \
     3     7   
    / \   / \
   2   4 6   8
low = 4
high = 7
Output: 
        5
      /   \
     4     8

Input: 
        5
      /   \
     3     7   
    / \   / \
   2   4 6   8
low = 6
high = 7
Output: 
        7
      /   
     6

Recursive

fun trimBST(root: TreeNode?, low: Int, high: Int): TreeNode? {
    if (root == null) return null
    if (root.`val` < low) return trimBST(root.right, low, high)
    else 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
}

• Time Complexity: O(n).
• Space Complexity: O(h).

// TODO: practice iterative way https://leetcode.com/problems/trim-a-binary-search-tree/solutions/107026/java-solution-iteration-version/

起始先从给定的 root 进行出发，找到第一个满足值符合 [low,high] 范围的节点，该节点为最后要返回的根节点 ans。

随后考虑如何修剪 ans 的左右节点：当根节点符合 [low,high] 要求时，修剪左右节点过程中仅需考虑一边的边界值即可。即对于 ans.left 只需考虑将值小于 low 的节点去掉（因为二叉搜索树的特性，ans 满足不大于 high 要求，则其左节点必然满足）；同理 ans.right 只需要考虑将大于 high 的节点去掉即可。

https://leetcode.cn/problems/trim-a-binary-search-tree/solutions/1814532/by-ac_oier-help/