Day 22 二叉樹(shù)

235. 二叉搜索樹(shù)的最近公共祖先

根據(jù)二叉搜索樹(shù)的性質(zhì)，相比普通二叉樹(shù)可以極大程度的簡(jiǎn)化代碼，作為公共祖先其值一定在兩個(gè)給定節(jié)點(diǎn)值之間，從樹(shù)根往下遍歷，第一次出現(xiàn)兩個(gè)給定節(jié)點(diǎn)值之間的值，那個(gè)節(jié)點(diǎn)即為最近公共祖先（為什么是最近不是最遠(yuǎn)？根節(jié)點(diǎn)一般為最遠(yuǎn)，第一次出現(xiàn)的值處于兩個(gè)給定節(jié)點(diǎn)值之間的節(jié)點(diǎn)為最近）

遞歸法

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

迭代法

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val > q->val)
        {
            swap(p, q);
        }

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

        return nullptr;
    }
};

代碼隨想錄里的解法更加簡(jiǎn)潔

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

701. 二叉搜索樹(shù)中的插入操作

沒(méi)有要求平衡再簡(jiǎn)單不過(guò)，直接按搜索的方式遍歷到最后一個(gè)葉子節(jié)點(diǎn)，在葉子節(jié)點(diǎn)下添加新的節(jié)點(diǎn)就可以了

迭代法

用迭代法簡(jiǎn)單明了

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode *cur = root, *pre = nullptr;
        while (cur)
        {
            pre = cur;
            if (cur->val < val)
            {
                cur = cur->right;
            }
            else if (cur->val > val)
            {
                cur = cur->left;
            }
        }

        if (pre)
        {
            if (pre->val < val)
            {
                pre->right = new TreeNode(val);
            }
            else
            {
                pre->left = new TreeNode(val);
            }
            return root;
        }
        else return new TreeNode(val);
    }
};

遞歸法

記住要記錄父節(jié)點(diǎn)，就有大概的思路了

class Solution {
    TreeNode *parent= nullptr;

    void traversal(TreeNode *root, int val)
    {
        if (!root)
        {
            TreeNode *node = new TreeNode(val);
            if (parent->val < val) parent->right = node;
            else parent->left = node;
            return;
        }
        parent = root;

        if (root->val < val) traversal(root->right, val);
        if (root->val > val) traversal(root->left, val);  
    }

public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        traversal(root, val);
        return root;      
    }
};

450. 刪除二叉搜索樹(shù)中的節(jié)點(diǎn)

寫(xiě)麻了，涉及到結(jié)構(gòu)調(diào)整，有點(diǎn)難

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

        return root;
    }
};

刪除節(jié)點(diǎn)太難了，這里就不寫(xiě)迭代了。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-584661.html

到了這里，關(guān)于算法刷題Day 22 二叉搜索樹(shù)的最近公共祖先+二叉搜索樹(shù)中的插入操作+刪除二叉搜索樹(shù)中的節(jié)點(diǎn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！