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

代码随想录-笔记-其五

article 2024/11/29 5:34:58

二叉树

合并二叉树

617. 合并二叉树 - 力扣（LeetCode）

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

递归：

/**
 * 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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1)return root2;
        if(!root2)return root1;
        TreeNode* res=new TreeNode(root1->val+root2->val);
        res->left=mergeTrees(root1->left, root2->left);
        res->right=mergeTrees(root1->right, root2->right);
        return res;
    }
};

思路非常的简单，把要返回的结果和两个树的节点同步就行，两个节点都有就加起来，缺一个就返回另一个，递归即可。

迭代：

/**
 * 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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1)return root2;
        if(!root2)return root1;
        TreeNode* res=new TreeNode(root1->val+root2->val);
        queue<pair<TreeNode*,pair<TreeNode*,TreeNode*>>> q;
        q.push({res,{root1,root2}});
        while(!q.empty()){
            auto [cur,roots]=q.front();
            q.pop();
            auto [root1,root2]=roots;
            if(root1->left&&root2->left){
                cur->left=new TreeNode(root1->left->val+root2->left->val);
                q.push({cur->left,{root1->left,root2->left}});
            }
            else if(root1->left){
                cur->left=root1->left;
            }
            else if(root2->left){
                cur->left=root2->left;
            }
            if(root1->right&&root2->right){
                cur->right=new TreeNode(root1->right->val+root2->right->val);
                q.push({cur->right,{root1->right,root2->right}});
            }
            else if(root1->right){
                cur->right=root1->right;
            }
            else if(root2->right){
                cur->right=root2->right;
            }
        }
        return res;
    }
};

迭代的步骤要复制一些，但本身的原理是不变的。

二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

/**
 * 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:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> temp;
        while(root||!stk.empty()){
            while(root){
                stk.push(root);
                root=root->left;
            }
            root=stk.top();
            stk.pop();
            temp.push_back(root->val);
            root=root->right;
        }
        int res=INT_MAX;
        for(int i=1;i<temp.size();i++){
            res=min(res,temp[i]-temp[i-1]);
        }
        return res;
    }
};

这个题主要运用到的性质：二叉搜索树的中序遍历得到的数组本身就是一个有序数组，因此我们只要对BST进行中序遍历后再遍历数组得到最小差值即可。

二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

/**
 * 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:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        unordered_map<int,int> mp;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            TreeNode* node=stk.top();
            stk.pop();
            mp[node->val]++;
            if(node->left)stk.push(node->left);
            if(node->right)stk.push(node->right);
        }
        int num=0;
        for(auto it=mp.begin();it!=mp.end();it++){
            num=max(num,it->second);
        }
        for(auto it=mp.begin();it!=mp.end();it++){
            if(it->second==num){
                res.push_back(it->first);
            }
        }
        return res;
    }
};

一开始呢我想到的就是使用哈希表记录每个二叉树节点的值之后找到那个出现次数最大的值，这个方法本身也没有问题，但是显然没有充分利用二叉搜索树的性质：中序遍历后是有序数组。

/**
 * 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:
    int maxCount=0;
    int count=0;
    TreeNode* pre=nullptr;
    vector<int> res;
    void helper(TreeNode* cur){
        if(!cur)return;
        helper(cur->left);
        if(!pre)count=1;
        else if(pre->val==cur->val)count++;
        else count=1;
        pre=cur;
        if(count==maxCount)res.push_back(cur->val);
        else if(count>maxCount){
            maxCount=count;
            res.clear();
            res.push_back(cur->val);
        }
        helper(cur->right);
        return;
    }
    vector<int> findMode(TreeNode* root) {
        helper(root);
        return res;
    }
};

二叉树的最近公共祖先

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

/**
 * 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==p||root==q||root==nullptr)return root;
        TreeNode* left=lowestCommonAncestor(root->left, p, q);
        TreeNode* right=lowestCommonAncestor(root->right, p, q);
        if(left&&right)return root;
        if(left)return left;
        return right;
    }
};

这个是二叉树最近公共祖先的标准写法了，非常的言简意赅。

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

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

/**
 * 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==p||root==q||root==nullptr)return root;
        TreeNode* left=lowestCommonAncestor(root->left, p, q);
        TreeNode* right=lowestCommonAncestor(root->right, p, q);
        if(left&&right)return root;
        if(left)return left;
        return right;
    }
};

上个题的二叉树的最近公共祖先的写法在这可以用吗？当然可以；

但也不乏其他的写法如：

/**
 * 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;
    }
};

利用二叉搜索树的性质：如果根节点的值比两个点的值都大说明真正的最近公共祖先在左边，反之在右边（BST中的最近公共祖先肯定满足比一个节点的值大的同时比另一个节点的值小）。

又或者写成迭代式的：

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. 二叉搜索树中的插入操作 - 力扣（LeetCode）

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 任意有效的结果 。

递归：

/**
 * 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* parent;
    void helper(TreeNode* cur, int val){
        if(!cur){
            TreeNode* node=new TreeNode(val);
            if(parent->val>val)parent->left=node;
            else parent->right=node;
            return;
        }
        parent=cur;
        if(cur->val<val)helper(cur->right, val);
        if(cur->val>val)helper(cur->left, val);
        return;
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root){
            root=new TreeNode(val);
        }
        helper(root, val);
        return root;
    }
};

迭代：

/**
 * 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){
            root=new TreeNode(val);
            return root;
        }
        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）

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

/**
 * 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;
        else if(!root->left&&!root->right&&root->val==key){
            delete root;
            return nullptr;
        }
        else if(!root->left&&root->val==key){
            auto resroot=root->right;
            delete root;
            return resroot;
        }
        else if(!root->right&&root->val==key){
            auto resroot=root->left;
            delete root;
            return resroot;
        }
        else if(root->val==key){
            TreeNode* cur=root->right;
            while(cur->left){
                cur=cur->left;
            }
            cur->left=root->left;
            TreeNode* temp=root;
            root=root->right;
            delete temp;
            return root;
        }
        if(root->val>key)root->left=deleteNode(root->left, key);
        if(root->val<key)root->right=deleteNode(root->right, key);
        return root;
    }
};

删除的步骤相比插入要麻烦得多，因为插入只用考虑在叶子节点上操作，而删除会涉及到二叉树的结构的变化。这里的删除包含五种可能的情况：没有找到要删除的节点，找到删除的节点且：只有左子树，只有右子树，左右子树都没有，左右子树都有。最麻烦的是最后一种情况，我们需要去找到节点的右子树的最左边节点，将其放在删除节点的左子树部分，然后我们删除节点即可。

修剪二叉搜索树

669. 修剪二叉搜索树 - 力扣（LeetCode）

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

递归：

/**
 * 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* trimBST(TreeNode* root, int low, int high) {
        if(!root)return nullptr;
        if(root->val<low){
            return trimBST(root->right,low,high);
        }
        else if(root->val>high){
            return trimBST(root->left,low,high);
        }
        root->left=trimBST(root->left, low, high);
        root->right=trimBST(root->right, low, high);
        return root;
    }
};

迭代：

/**
 * 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* trimBST(TreeNode* root, int low, int high) {
        if(!root)return nullptr;
        while(root&&(root->val<low||root->val>high)){
            if(root->val<low)root=root->right;
            else root=root->left;
        }
        TreeNode* cur=root;
        while(cur){
            while(cur->left&&cur->left->val<low){
                cur->left=cur->left->right;
            }
            cur=cur->left;
        }
        cur=root;
        while(cur){
            while(cur->right&&cur->right->val>high){
                cur->right=cur->right->left;
            }
            cur=cur->right;
        }
        return root;
    }
};

将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

/**
 * 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* helper(vector<int>& nums,int l,int r){
        if(l>r)return nullptr;
        int mid=l+(r-l)/2;
        TreeNode* root=new TreeNode(nums[mid]);
        root->left=helper(nums, l, mid-1);
        root->right=helper(nums,mid+1,r);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0)return nullptr;
        return helper(nums,0,nums.size()-1);
    }
};

二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

class Solution {
private:
    int pre; // 记录前一个节点的数值
    void traversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->right;   // 右
            } else {
                cur = st.top();     // 中
                st.pop();
                cur->val += pre;
                pre = cur->val;
                cur = cur->left;    // 左
            }
        }
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

查看全文

http://www.kler.cn/a/413769.html