day22 二叉树(八)

2023-12-20 16:00:23

day22
代码随想录
2023.12.20

1. 235二叉搜索树的最近公共祖先
与昨天的不同,今天是二叉搜索树,不用在回溯挨个找节点了,要利用二叉搜索树的性质,两个结点的最近公共祖先,一定满足该节点值在【p,q】之间,如果全部大于qp,则说明pq在左子树,如果全部小于pq,则说明在右子树,这递归逻辑不就出来了!

/**
 * 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) {
        return travel(root,p,q);
    }
    TreeNode* travel(TreeNode*node, TreeNode*p, TreeNode*q){
        if(node==NULL) return NULL;
        if(node->val > p->val && node->val > q->val){
            TreeNode*left = travel(node->left,p,q);
            if(left!=NULL)
                return left;
        }
        if(node->val < p->val && node->val < q->val){
            TreeNode*right = travel(node->right,p,q);
            if(right!=NULL)
                return right;
        }
        return node;
    }
};

2. 701二叉搜索树的插入操作
这道题刚看,确实有点吓到我了,以为要调整树的结构,因为记得二叉搜索树是平衡二叉树啊。但是看了文字讲解,说不用调整结构,就有点懵,看了看关于二叉搜索树的知识点,原来:平衡二叉树是二叉搜索树,二叉搜索树不一定是平衡二叉树,所以不用调整结构,往下一直加节点就ok!这具体操作就很简单了,往下递归呗,直到空,那就新增一个节点。

/**
 * 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==NULL){
            TreeNode* node = new TreeNode(val);
            return node;
        }
        travel(root, val);
        return root;
    }
    void travel(TreeNode*node, int val){
        if(val > node->val){
            if(node->right)
                travel(node->right, val);
            else{
                TreeNode*temp = new TreeNode(val);
                node->right = temp;
            }
        }
        if(val < node->val){
            if(node->left)
                travel(node->left,val);
            else{
                TreeNode*temp = new TreeNode(val);
                node->left = temp;
            }
        }
        
    }
};

3. 450删除二叉搜索树中的节点
这题第一眼看,感觉很麻烦,找到节点后,删除后,删除节点的左右子树怎么协调,情况有很多种,难道挨个if?最后看文字讲解,emm确实是多种情况分别处理,不过,没我想的那么复杂,大体来说,当找到删除节点,该节点无非四种情况,

  1. 是叶子节点(左右子树都为空),此时直接删除就行
  2. 左子树为空,那么右子树直接取代根节点就行
  3. 右子树为空,左子树直接取代根节点就行
  4. 最后一种则是左右子树都存在,这是要满足最后结果也是二叉搜索树,只能将右子树作为根节点,而左子树要插入到右子树中,要知道,右子树一定是都大于左子树的,而要把左子树插入到右子树中,只能找到右子树的最小值,作为该节点的左子树上,而一棵树的最小值不就是最左边的那个节点嘛,所以这种情况的处理也就清楚了
/**
 * 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==NULL) return root;
        if(root->val == key){
            if(root->left==NULL && root->right==NULL){//删除节点左右子树都为空
                delete root;
                return NULL;
            }
            else if(root->left==NULL && root->right!=NULL){//左空,右不为空
                TreeNode*temp = root->right;
                delete root;
                return temp;
            }
            else if(root->right==NULL && root->left!=NULL){//右空,左不为空
                TreeNode*temp = root->left;
                delete root;
                return temp;
            }
            else{
                TreeNode*temp = root->right;
                while(temp->left){
                    temp = temp->left;
                }//此时temp就是右子树的最小节点
                TreeNode* node = root->right;
                temp->left = root->left;
                delete root;
                return node;
            }
        }
        if(root->val > key) root->left = deleteNode(root->left, key);
        if(root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

文章来源:https://blog.csdn.net/qq_56913257/article/details/135101224
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。