LeetCode冲刺：Day16

发布于 2022-11-23  82 次阅读

今天把随想录的二叉树部分刷完了第一遍。

1. 二叉搜索树的最小绝对差

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

直接对比父节点与两子节点的差找出最小值，但此法不可行，还是放到数组中去遍历。

答案给出了遍历树的写法，用一个指针记录前一个结点，在取最小差值时，是对比前一个结点和当前节点的差值，而非父子结点间差值，显然这样的思路是合理的。

代码

class Solution {
private:
    void inorder(TreeNode* root,vector<int>& nums) {
        if (root==nullptr) return;
        inorder(root->left,nums);
        nums.push_back(root->val);
        inorder(root->right,nums);
    }
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> nums;
        inorder(root,nums);
        int ans=INT_MAX;
        for (int i=1;i<nums.size();++i) {
            ans=min(ans,nums[i]-nums[i-1]);
        }
        return ans;
    }
};

2. 二叉搜索树中的众数

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

遍历一遍树，记录元素频数；遍历map，找到最大频数；遍历map，将频数等于最大频数的元素加入ans。

对于搜索树，可以利用其性质，相同元素必然相邻，用一个变量统计当前元素次数，如果等于maxCnt，就加入结果数组。当遇到大于maxCnt的计数，应当把结果集清空，重新加入当前元素，这样可以达到常数空间。

代码

class Solution {
private:
    map<int,int> mp;
    void dfs(TreeNode* root) {
        if (!root) return;
        mp[root->val]++;
        dfs(root->left);
        dfs(root->right);
    }
public:
    vector<int> findMode(TreeNode* root) {
        mp.clear();
        int maxFreq=INT_MIN;
        dfs(root);
        for (auto& elem:mp) maxFreq=max(maxFreq,elem.second);
        vector<int> ans;
        for (auto& elem:mp) if (elem.second==maxFreq) ans.push_back(elem.first);
        return ans;
    }
};

常数空间版：

class Solution {
private:
    TreeNode* pre;
    vector<int> ans;
    int cnt=0;
    int maxCnt=0;
    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);

        if (!pre) {
            cnt=1;
            maxCnt=1;
            ans.push_back(root->val);
        } else {
            if (root->val==pre->val) {
                ++cnt;
                if (cnt>maxCnt) {
                    ans.clear();
                    maxCnt=cnt;
                }
            } else cnt=1;
            if (cnt==maxCnt) ans.push_back(root->val);
        }
        pre=root;

        dfs(root->right);
    }
public:
    vector<int> findMode(TreeNode* root) {
        ans.clear();
        pre=nullptr;
        cnt=0;
        maxCnt=0;
        dfs(root);
        return ans;
    }
};

3. 二叉树的最近公共祖先

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

要找祖先节点，需要从下到上遍历，或者说需要回溯。而对于二叉树来说，后序遍历就是天然的回溯。

看到二叉树相关题目，首先就应该想到能不能遍历，用什么顺序遍历；不能遍历就想能不能放到数组里做。

代码

class Solution {
private:
    TreeNode* ans;
    bool postorder(TreeNode* root,TreeNode* p,TreeNode* q) {
        if (!root) return false;
        bool left=postorder(root->left,p,q);
        bool right=postorder(root->right,p,q);
        if ((left&&right)||((root==p||root==q)&&(left||right))) {
            ans=root;
            return false;
        }
        if (root==p||root==q||left||right) return true;
        return false;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        ans=nullptr;
        postorder(root,p,q);
        return ans;
    }
};

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

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

利用搜索树的性质，自顶向下遍历，遇到的第一个在pq之间的结点，即为所求。

代码

class Solution {
private:
    TreeNode* ans;
    void dfs(TreeNode* root,int& p,int&  q) {
        if (root==nullptr) return;

        if (root->val>=p&&root->val<=q) {
            ans=root;
            return;
        }
        else if (root->val<p) dfs(root->right,p,q);
        else dfs(root->left,p,q);
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        ans=nullptr;
        int low=min(p->val,q->val);
        int high=max(p->val,q->val);
        dfs(root,low,high);
        return ans;
    }
};

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

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

只是要求插入二叉搜索树，而非平衡二叉搜索树，所以较为简单。

如果是平衡树，在插入后还需要做调平操作。如果不考虑时间复杂度，甚至可以把原有平衡二叉树还原成数组，插入新元素后再从数组重新构造二叉树。

代码

class Solution {
private:
    void insert(TreeNode* root,int& val) {
        if (val<root->val) {
            if (!root->left) {
                TreeNode* left=new TreeNode(val);
                root->left=left;
                return;
            } else insert(root->left,val);
        } else {
            if (!root->right) {
                TreeNode* right=new TreeNode(val);
                root->right=right;
                return;
            } else insert(root->right,val);
        }
    }
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) {
            TreeNode* ans=new TreeNode(val);
            return ans;
        }
        insert(root,val);
        return root;
    }
};

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

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

辅助函数跟主函数名字有点相似，调用的时候不小心掉用了自己，我说怎么一直死循环……改完就好了。

采用返回结点的递归方式，更方便一些。先写个辅助函数，用于将结点插入到树中。删除时，如果当前结点值不等于目标值，根据大小关系递归调用左子结点或右子结点。如果相等，分情况讨论，没有孩子，则直接返回空指针；有一个孩子，则返回那个孩子；如果两个都存在，用辅助函数把左孩子插到右孩子上去，再返回右孩子即可。

随想录在孩子插入孩子的过程中是直接找右孩子的最左空结点，也是一样的，但我这个辅助函数更通用一些。

代码

class Solution {
private:
    TreeNode* insert(TreeNode* root,TreeNode* child) {
        if (!root) return child;
        if (root->val<child->val) root->right=insert(root->right,child);
        else root->left=insert(root->left,child); 
        return root;
    }
    TreeNode* delNode(TreeNode* root, int& key) {
        if (!root) return root;
        if (root->val==key) {
            if (!root->left&&!root->right) return nullptr;
            else if (!root->left&&root->right) return root->right;
            else if (root->left&&!root->right) return root->left;
            else {
                root->right=insert(root->right,root->left);
                return root->right;
            }
        } else if (root->val<key) {
            root->right=delNode(root->right,key);
        } else {
            root->left=delNode(root->left,key);
        }
        return root;
    }
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        return delNode(root,key);
    }
};

7. 修剪二叉搜索树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

初看比较复杂。但实际上情况也有限，依然使用返回结点的递归。

  1. 如果当前节点在范围内（左闭右闭），递归调用修剪左右孩子。
  2. 如果结点值小于下界，则其左孩子肯定不要了，递归修剪其右孩子并返回。
  3. 如果结点值大于上界，则其右孩子肯定不要了，递归修剪其左孩子并返回。

代码

class Solution {
private:
    TreeNode* trim(TreeNode* root, int low, int high) {
        if (!root) return root;
        if (root->val>=low&&root->val<=high) {
            root->left=trim(root->left,low,high);
            root->right=trim(root->right,low,high);
            return root;
        } else if (root->val<low) {
            return trim(root->right,low,high);
        } else return trim(root->left,low,high);
    }
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        return trim(root,low,high);
    }
};

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

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

每次将当前区间中间元素作为根节点即可，并递归调用左区间作为左子树，右区间作为右子树。

代码

class Solution {
private:
    TreeNode* dfs(const vector<int>& nums,int low,int high) {
        TreeNode* root;
        if (low>high) root= nullptr;
        else if (low==high) {
            root=new TreeNode(nums[low]);
        } else {
            int mid=low+(high-low)/2;
            root=new TreeNode(nums[mid]);
            root->left=dfs(nums,low,mid-1);
            root->right=dfs(nums,mid+1,high);
        }
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return dfs(nums,0,nums.size()-1);
    }
};

9. 把二叉搜索树转换为累加树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

两种做法，一个是中序遍历把结点全都放到数组中，从后向前累加，需要n的额外空间。

第二个是中序遍历（左右互换），另设一个指针pre（初始化成值为零的结点），用于记录前一个结点，依次累加即可，只需要常数空间。

代码

方法一：

class Solution {
private:
    void inorder(TreeNode* root,vector<TreeNode*>& tree) {
        if (!root) return;
        inorder(root->left,tree);
        tree.push_back(root);
        inorder(root->right,tree);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        vector<TreeNode*> tree;
        inorder(root,tree);
        for (int i=tree.size()-2;i>=0;--i) tree[i]->val+=tree[i+1]->val;
        return root;
    }
};

方法二：

class Solution {
private:
    TreeNode* pre;
    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->right);
        root->val+=pre->val;
        pre=root;
        inorder(root->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre=new TreeNode(0); //可以再初始化一个指针，用于保存一开始的pre，最后delete
        inorder(root);
        return root;
    }
};