*算法训练（leetcode）第十七天 | 235. 二叉搜索树的最近公共祖先、701. 二叉搜索树中的插入操作、450. 删除二叉搜索树中的节点

235. 二叉搜索树的最近公共祖先

leetcode题目地址

二叉搜索树（BST），左小右大。在BST中查找两个节点p、q的最近公共祖先时，使用前序遍历，访问到的第一个在两个节点的区间内[p, q]的节点就是公共祖先节点。当前节点值超出区间时借助BST性质（左小右大）向对应的方向缩小范围。

递归

时间复杂度： $O(logn)$
空间复杂度： $O(logn)$

相当于二分查找，访问的是头结点到目标节点路径上的结点，所以时间复杂度最坏是树高logn，空间复杂度是递归的压栈空间，也是树高logn。

// c++
/**
 * 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* inOrder(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode* &result){
        if(!root) return nullptr;
        if(root->val <= q->val && root->val >= p->val) {
            // result = root;
            return root;
        }    
        if(root->val > q->val) return inOrder(root->left, p, q, result);
        if(root->val < p->val) return inOrder(root->right, p, q, result);
        return nullptr;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 保证p保存较小值，q保存较大值
        if(p->val > q->val) swap(p, q);
        TreeNode* result=nullptr;
        return inOrder(root, p, q, result);
        // return result;
    }
};

非递归

时间复杂度： $O(logn)$
空间复杂度： $O(1)$

和递归一样，时间复杂度是树高logn，这里没有使用额外空间，所以空间复杂度是O(1)。

// c++
/**
 * 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) return root;
        if(p->val > q->val) swap(p, q);
        
        while(root){
            if(root->val < p->val){
                root = root->right;
            }else if(root->val > q->val){
                root = root->left;
            }else{
                return root;
            }
        }
        return nullptr;
    }
};

701. 二叉搜索树中的插入操作

leetcode题目地址

中序遍历(什么序遍历都可以，这里使用的是中序)，找当前节点大于目标值且左子树为空或者当前节点小于目标值且右子树为空的节点，该结点即为目标值插入的父节点，然后将目标值插入对应位置既可。

时间复杂度： $O(logn)$
空间复杂度： $O(logn)$

递归

// c++
/**
 * 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:

    void inOrder(TreeNode* root, int val){
        if(!root) return;

        if(val < root->val) inOrder(root->left, val); // 左
        
        if(root->val > val && !root->left) {
            root->left = new TreeNode(val);
            return;
        }else if(root->val < val && !root->right){
            root->right = new TreeNode(val);
            return;
        }
        
        if(val > root->val) inOrder(root->right, val);  // 右
    }

    TreeNode* insertIntoBST(TreeNode* root, int val) {
    	// 空树直接返回新节点
        if(!root) return new TreeNode(val);
        inOrder(root, val);
        return root;
    }
};

非递归

// c++
/**
 * 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) {
        TreeNode* head = root;
        TreeNode* parent = root;

        while(root){
            parent = root;
            if(root->val > val) root = root->left;
            else root = root->right;
        }

        if(!parent) return new TreeNode(val);
        if(parent->val > val) parent->left = new TreeNode(val); 
        else parent->right = new TreeNode(val);

        return head;
    }
};

*450. 删除二叉搜索树中的节点

leetcode题目地址

删除二叉搜索树中节点后需要任保持二叉搜索树的特性（左小右大）。因此在删除结点时分为以下几种情况：

• 没有找到目标节点，返回当前节点；
• 目标节点是叶结点（左右孩子为空），直接删除，返回nullptr；
• 目标节点有一个孩子（左孩子或右孩子非空），则用其孩子节点替换目标节点位置，即删除目标节点，返回孩子节点。
• 目标节点有两个孩子（左右孩子均非空），则可以用任意一个孩子节点替换目标节点，另一个孩子节点放到对应位置：
• • 使用左孩子替换目标节点，则把右孩子放到左孩子的最右结点（中序遍历中目标节点的前一个结点位置）
• • 使用右孩子替换目标节点，则把左孩子放到右孩子的最左节点（中序遍历中目标节点的后一个结点位置）

删除目标节点，返回对应孩子节点。

时间复杂度： $O(logn)$
空间复杂度： $O(logn)$

// c++
/**
 * 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->val == key){
            // 叶结点直接删除，返回nullptr
            if(!root->left && !root->right){
                delete root;
                return nullptr;
            }
            // 只有左孩子，返回左孩子
            if(root->left && !root->right) {
                TreeNode* tmp = root;
                root = root->left;
                delete tmp;
                return root; 
            }
            // 只有右孩子，返回右孩子
            if(root->right && !root->left){
                TreeNode* tmp = root;
                root = root->right;
                delete tmp;
                return root; 
            }   
            // 左右孩子都有  用右孩子替代
            if(root->left && root->right){
                TreeNode *tmp = root;
                TreeNode *node = root->right;
                while(node->left){
                    node = node->left;
                }
                root = root->right;
                delete tmp;
                node->left = root->left;
                return root;
            }
        }
        // 继续向左右子树缩小查找域
        if(root->val > key) root->left = deleteNode(root->left, key);
        if(root->val < key) root->right = deleteNode(root->right, key);
        // 没找到 将自己返回
        return root;
    }
};