代码随想录-训练营-day17

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val>p->val&&root->val>q->val)return lowestCommonAncestor(root->left, p, q);
        if(root->val<p->val&&root->val<q->val)return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};

虽然代码看着很简单，但是其实这其中的逻辑相对来说很复杂，二叉搜索树比起二叉树来说找公共祖先更方便，我们可以直接根据给定的点的值与根节点的值进行比较来确定大概的位置，大大减少了遍历需要的时间与复杂度。

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

二叉搜索树的插入比较简单，我们直接根据值的大小锁定位置后再插入即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root){
            TreeNode* node=new TreeNode(val);
            return node;
        }
        TreeNode* cur=root,* parent=root;
        while(cur){
            parent=cur;
            if(cur->val>val)cur=cur->left;
            else cur=cur->right;
        }
        TreeNode* node=new TreeNode(val);
        if(parent->val>val)parent->left=node;
        else parent->right=node;
        return root;
    }
};

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

删除相对来说要麻烦一些，因为删除节点往往会引起一部分乃至整个树的结构进行改变，我们需要考虑当前节点是需要删除的节点时他的左子树与右子树的变化情况。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root)return nullptr;
        if(!root->left&&!root->right&&root->val==key){
            delete root;
            return nullptr;
        }
        else if(!root->left&&root->val==key){
            TreeNode* res=root->right;
            delete root;
            return res;
        }
        else if(!root->right&&root->val==key){
            TreeNode* res=root->left;
            delete root;
            return res;
        }
        else if(root->val==key){
            TreeNode* cur=root->right;
            while(cur->left){
                cur=cur->left;
            }
            cur->left=root->left;
            TreeNode* tem=root;
            root=root->right;
            delete tem;
            return root;
        }
        if(root->val>key)root->left=deleteNode(root->left,key);
        if(root->val<key)root->right=deleteNode(root->right,key);
        return root;
    }
};

能够看到当我们处理二叉搜索树时采用递归遍历的方法明显多了起来，这是因为我们喜欢用递归的方法进行中序遍历转化为有序遍历，把更多时间留在处理节点的具体情况上。