我真的不想刷题!! T_T
剑指 Offer 33. 二叉搜索树的后序遍历序列
题目描述:
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5
/ \
2 6
/ \
1 3
示例 1:
输入: [1,6,3,2,5]
输出: false
示例 2:
输入: [1,3,2,6,5]
输出: true
code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public:
bool verifyPostorder(vector<int>& postorder) { stack<int> s; int root = INT_MAX; for(int i = postorder.size() - 1; i >= 0; i--){ if(postorder[i] > root){ return false; } while(!s.empty() && postorder[i] < s.top()){ root = s.top(); s.pop(); } s.push(postorder[i]); } return true; } };
|
剑指 Offer 36. 二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public: Node *pre = nullptr, *head = nullptr; void dfs(Node* root){ if(!root) return; dfs(root -> left); if (pre) pre->right = root; else head = root; root->left = pre; pre = root; dfs(root->right); } Node* treeToDoublyList(Node* root) { if (!root) return root; dfs(root); head->left = pre; pre->right = head; return head; } };
|
剑指 Offer II 078. 合并排序链表
题目描述
给定一个链表数组,每个链表都已经按升序排列。
请将所有链表合并到一个升序链表中,返回合并后的链表。
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
| class Solution { public: struct cmp{ bool operator() (ListNode* a, ListNode* b){ return a -> val > b -> val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode *, vector<ListNode *>, cmp> pq; ListNode* dummy = new ListNode(0); for(auto p : lists){ if(p) pq.push(p); } ListNode* t = dummy; while(!pq.empty()){ t -> next = pq.top(); t = pq.top(); pq.pop(); if(t->next){ pq.push(t->next); } } return dummy->next;
} };
|
剑指 Offer II 106. 二分图
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
| class Solution { public: bool isBipartite(vector<vector<int>>& graph) { int n = graph.size(); if(n == 0){ return true; } vector<int> color(n, 0); queue<int> q; for(int i = 0; i < n; i++){ if(!color[i]){ q.push(i); color[i] = 1; } while(!q.empty()){ int node = q.front(); q.pop(); for(const int & j : graph[node]){ if(color[j] == 0){ color[j] = color[node] == 2 ? 1 : 2; q.push(j); } else if(color[node] == color[j]) return false; } } } return true; } };
|
Gitalking ...