当前位置：首页 > article >正文

[代码随想录20二叉树]二叉树的公共祖先问题

article 2025/2/1 2:54:43

前言

二叉树的公共祖先都是老朋友了，但是搜索二叉树的题目，相对于简单一点，因为他本身是有序的，所以我们需要函数自己参数去递归或者迭代，也可以通过新建函数去递归，通过两个父子指针去迭代。

题目链接

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

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

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

一、二叉搜索树的最近公共祖先

递归思路：搜索二叉树本身就是有序的，所以我们寻找最近公共祖先可以天然借助二叉树的有序性，同时只要保证递归的值，能在这个根节点中找到，就行。

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

迭代思路：直接把递归修改root的逻辑，换成赋值操作就行，这是最爽的一次迭代操作，思路也很清楚。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root){
            if(root->val>p->val&&q->val<root->val){
            root=root->left;
            }else if(root->val<p->val&& root->val<q->val){
            root=root->right;
            }else return root;
        }
        return NULL;
    }

二、二叉搜索树的插入操作

递归思路：插入元素，我们需要对搜索二叉树，只需要进行判定即可，因为他本身就是有序的，直接递归或者迭代一下就能找着位置。

迭代的思路：上阵父子兵，儿子去找位置，父亲放元素，哈哈哈我自己总结的。

TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr){
            TreeNode* node=new TreeNode(val);
            return node;
        }
        if(root->val>val)root->left=insertIntoBST(root->left,val);
        if(root->val<val)root->right=insertIntoBST(root->right,val);
        return root;
    }

TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr){
            TreeNode* node=new TreeNode(val);
            return node;
        }
        TreeNode* cur=root;
        TreeNode*parent=root;//上阵父子兵
        //儿子去找位置
        while(cur!=nullptr){
            parent=cur;
            if(cur->val>val)cur=cur->left;
            else cur=cur->right;
        }
        TreeNode *node=new TreeNode(val);
        //接下在父亲后面。
        if(val>parent->val)parent->right=node;
        else parent->left=node;
        return root;
    }

三、删除搜索二叉树的节点

递归思路：五个条件一路顺下来就行

TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr)return root;
        if(root->val==key){
            if(root->left==nullptr&&root->right==nullptr){
                delete root;
                return nullptr;
            }else if(root->left==nullptr){
                auto retNode=root->left;
                delete root;
                return retNode;
            }else if(root->right==nullptr){
                auto retNode=root->right;
                delete root;
                return retNode;
            }else{
                TreeNode*cur=root->right;
                while(cur->left!=nullptr)cur=cur->left;
                cur->left=root->left;
                TreeNode*tmp=root;
                root=root->right;
                delete tmp;
                return root;
            }
        }
        if(root->val>key)root->left=deleteNode(root->left,key);
        if(root->val<key)root->right=deleteNode(root->right,key);
        return root;
    }