#include "s0669_trim_a_binary_search_tree.hpp"

TreeNode* S0669::trimBST(TreeNode* root, int low, int high) {
  if (root == nullptr) return nullptr;
  if (low <= root->val && root->val <= high) {
    // 如果根节点的值位于范围内，则对左右子树进行剪裁
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
  } else if (root->val < low) {
    // 如果根节点的值小于 low, 把根节点和左子树都剪裁掉
    return trimBST(root->right, low, high);
  } else {
    // 如果根节点的值大于 high, 把根节点和右子树都剪裁掉
    return trimBST(root->left, low, high);
  }
}