优先队列 priority_queue
仿函数less 升序 -》大根堆
仿函数greater 降序 -》 小根堆

仿函数-》重载()

1合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

思路：
将所有的节点放到优先队列中 一个一个拿出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    struct cmp {
        bool operator()(ListNode* l1, ListNode* l2) {
            return l1->val > l2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        for (auto head : lists) {
            if (head) {
                pq.push(head);
            }
        }

        ListNode* dummy =
            new ListNode(0); // 哨兵节点，作为合并后链表头节点的前一个节点
        auto cur = dummy;
        while (!pq.empty()) {     // 循环直到堆为空
            auto node = pq.top(); // 剩余节点中的最小节点
            pq.pop();
            if (node->next) { // 下一个节点不为空
                pq.push(node->next); // 下一个节点有可能是最小节点，入堆
            }
            cur->next = node; // 合并到新链表中
            cur = cur->next;  // 准备合并下一个节点
        }
        return dummy->next; // 哨兵节点的下一个节点就是新链表的头节点
    }
};

2最近公共祖先

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。
设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。

测试样例：

1
2
2，3
返回：1

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

class LCA {
public:
    int getLCA(int a, int b) {
        // write code here
        while(a!=b){
            if(a>b){
                a/=2;
            }else{
                b/=2;
            }
        }
        return a;
    }
};

3从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

实例

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

输出：[3,9,20,null,null,15,7]

先根据后序遍历得知根节点 在中序遍历中的通过根节点分为两部分 左子树 右子树 递归即可

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n=inorder.size();
        unordered_map<int,int> index;
        for(int i=0;i<n;i++){
            index[inorder[i]]=i;
        }

        function<TreeNode*(int,int,int,int)> dfs=[&](int in_l,int in_r,int post_l,int post_r)->TreeNode*{
            if(post_l==post_r) return nullptr;

            int left_size=index[postorder[post_r-1]]-in_l;
            TreeNode* left=dfs(in_l,in_l+left_size,post_l,post_l+left_size);
            TreeNode* right=dfs(in_l+left_size+1,in_r,post_l+left_size,post_r-1);
            return new TreeNode(postorder[post_r-1],left,right);
        };
        return dfs(0,n,0,n);
    }
};

4删除二叉搜索树中的节点

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

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

首先找到需要删除的节点；

如果找到了，删除它。

根据二叉搜索树的性质

如果目标节点大于当前节点值，则去右子树中删除；

如果目标节点小于当前节点值，则去左子树中删除；

如果目标节点就是当前节点，分为以下三种情况：

其无左子：其右子顶替其位置，删除了该节点；

其无右子：其左子顶替其位置，删除了该节点；

其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) 
    {
        if (root == nullptr)    return nullptr;
        if (key > root->val)    root->right = deleteNode(root->right, key);     // 去右子树删除
        else if (key < root->val)    root->left = deleteNode(root->left, key);  // 去左子树删除
        else    // 当前节点就是要删除的节点
        {
            if (! root->left)   return root->right; // 情况1，欲删除节点无左子
            if (! root->right)  return root->left;  // 情况2，欲删除节点无右子
            TreeNode* node = root->right;           // 情况3，欲删除节点左右子都有 
            while (node->left)          // 寻找欲删除节点右子树的最左节点
                node = node->left;
            node->left = root->left;    // 将欲删除节点的左子树成为其右子树的最左节点的左子树
            root = root->right;         // 欲删除节点的右子顶替其位置，节点被删除
        }
        return root;    
    }
};