目录

669 Trim a Binary Search Tree

题解

 代码

700. Search in a Binary Search Tree

题解

代码

108. Convert Sorted Array to Binary Search Tree

题解

代码

        333. Largest BST Subtree

代码

285 Inorder Successor in BST

题解

510 Inorder Successor in BSTII

题解

669 Trim a Binary Search Tree

题解

 

 

 代码

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root==NULL) return root;
        if(root->val >= low && root->val <= high){
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
            return root;
        }
        if(root->val < low){
            return trimBST(root->right, low, high);
        }
        return trimBST(root->left, low, high);
    }
    

};

700. Search in a Binary Search Tree 题解

二分的思想

代码

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == NULL) return NULL;
        if(root->val == val) return root;
        else if(root->val > val)  return searchBST(root->left, val);
        else return searchBST(root->right, val);
     }
};

108. Convert Sorted Array to Binary Search Tree 题解

每次取排好序的中间位置创造根节点，然后对于左半部分创建左子树，右半部分创建右子树。

代码

class Solution {
public:
    TreeNode* sortedArrayToBST(vector& nums) {
        if(nums.size()<1) return NULL;   
        TreeNode* root = buildBST(nums, 0, nums.size()-1 );
        return root;
    }
    
    TreeNode* buildBST(vector& nums, int start, int end){
        if(start > end) return NULL;
        int mid = (start + end) /2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = buildBST(nums, start, mid-1);
        root->right = buildBST(nums, mid+1, end);
        return root;
    }
};

333. Largest BST Subtree

如果用简单的方法做，就是先判断每个树是不是BST，如果是则返回其节点个数，如果不是就递归他的左右子树，最后结果要用最大值。

代码

class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        if (isBST(root, INT_MIN, INT_MAX)) {
            return countNodes(root);
        }
        return max(largestBSTSubtree(root->left), largestBSTSubtree(root->right));
    }
    bool isBST(TreeNode* root, int minVal, int maxVal) {
        if (!root) return true;
        if (root->val >= maxVal)
            return false;
        if (root->val <= minVal)
            return false;
        return isBST(root->left, minVal, root->val) && isBST(root->right, root->val, maxVal);
    }
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
private:
    int res = 0;
};

285 Inorder Successor in BST 题解

寻找给定节点的中序后继，直接根据二叉搜索树的性质去寻找的最大最小的节点。二分查找，分治的思想。

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* res = NULL;
        while (root) {
            if (p->val < root->val) {
                res = root;
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return res;
    }
};

510 Inorder Successor in BSTII 题解

这道题是之前的那道 Inorder Successor in BST 的后续，之前那道题给了我们树的根结点，而这道题并没有确定给我们根结点，只是给了树的任意一个结点，然后让求给定结点的中序后继结点。

后继结点出现的位置大致可以分为两类，一类是在子孙结点中，另一类是在祖先结点中。仔细观察例子不难发现，当某个结点存在右子结点时，其中序后继结点就在子孙结点中，反之则在祖先结点中。这样我们就可以分别来处理，当右子结点存在时，我们需要找到右子结点的最左子结点，这个不难，就用个 while 循环就行了。当右子结点不存在，我们就要找到第一个比其值大的祖先结点，也是用个 while 循环去找即可，参见代码如下：

class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        if (!node) return nullptr;
        Node *res = nullptr;
        if (node->right) {
            res = node->right;
            while (res && res->left) res = res->left;
        } else {
            res = node->parent;
            while (res && res->val < node->val) res = res->parent;
        }
        return res;
    }
};