669.md

669. Trim a Binary Search Tree

Leetcode link

解题思路

本题要求我们给 BST 剪枝， 可以用 dfs 的思想递归。

考虑到有两种情况：

1. 如果当前节点小于 low，则返回当前节点的右边子节点
2. 如果当前节点大于 high，则返回当前节点的左边子节点

接下来就可以针对 root->left 与 root->right 来递归了

C++

class Solution {
 public:
  TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (!root) {
      return nullptr;
    }

    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;
  }
};

Javascript

var trimBST = function(root, low, high) {
    if(!root) {
        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;
};