1.重建二叉樹

題目

題解

(遞歸) O(n)

遞歸建立整棵二叉樹：先遞歸創(chuàng)建左右子樹，然后創(chuàng)建根節(jié)點(diǎn)，并讓指針指向兩棵子樹。

前序遍歷（根 左 右）中序遍歷（左 根 右） 后序遍歷（左 右 根）

具體步驟如下：

1. 先利用前序遍歷找根節(jié)點(diǎn)：前序遍歷（根 左 右）的第一個(gè)數(shù)，就是根節(jié)點(diǎn)的值；
2. 在中序遍歷中找到根節(jié)點(diǎn)的位置 k，則 k 左邊是左子樹的中序遍歷（左 根 右），右邊是右子樹的中序遍歷；
3. 假設(shè)左子樹的中序遍歷的長度是 l，則在前序遍歷中，根節(jié)點(diǎn)后面的 l 個(gè)數(shù)，是左子樹的前序遍歷，剩下的數(shù)是右子樹的前序遍歷；
4. 有了左右子樹的前序遍歷和中序遍歷，我們可以先遞歸創(chuàng)建出左右子樹，然后再創(chuàng)建根節(jié)點(diǎn)；

時(shí)間復(fù)雜度分析

我們在初始化時(shí)，用哈希表(unordered_map<int,int>)記錄每個(gè)值在中序遍歷中的位置，這樣我們在遞歸到每個(gè)節(jié)點(diǎn)時(shí)，在中序遍歷中查找根節(jié)點(diǎn)位置的操作，只需要 O(1) 的時(shí)間。此時(shí)，創(chuàng)建每個(gè)節(jié)點(diǎn)需要的時(shí)間是 O(1)，所以總時(shí)間復(fù)雜度是 O(n)。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
//preorder前序遍歷（根 左 右），inorder中序遍歷（左 根 右）
class Solution {
public:unordered_map<int, int> pos; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = preorder.size();for (int i = 0; i < n; ++i)pos[inorder[i]] = i;  //用哈希表記錄每個(gè)值在中序遍歷中的位置 return dfs(preorder, inorder, 0, n - 1, 0, n - 1);    }//前序遍歷pre的范圍是[pl,pr], 中序遍歷in的范圍是[il,ir]TreeNode* dfs(vector<int>& pre, vector<int>& in, int pl, int pr, int il, int ir) {if (pl > pr) return NULL;int k = pos[pre[pl]] - il;  //尋找前序的根節(jié)點(diǎn)在中序遍歷中是在第幾個(gè)位置TreeNode* root = new TreeNode(pre[pl]); //生成新的根節(jié)點(diǎn)root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);return root;}
};

2.二叉樹的下一個(gè)節(jié)點(diǎn)

題目

題解

(模擬) O(h)

這道題目就是讓我們求二叉樹中給定節(jié)點(diǎn)的后繼。

中序遍歷（左 根 右）

分情況討論即可，如下圖所示：

1. （左 根 右）如果當(dāng)前節(jié)點(diǎn)有右兒子，則右子樹中最左側(cè)的節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)的后繼。比如F的后繼是H；
2. （左 根）如果當(dāng)前節(jié)點(diǎn)沒有右兒子，**則需要沿著father域一直向上找，找到第一個(gè)是其(這個(gè)其非當(dāng)前節(jié)點(diǎn))father左兒子的節(jié)點(diǎn)，該節(jié)點(diǎn)的father就是當(dāng)前節(jié)點(diǎn)的后繼。**比如當(dāng)前節(jié)點(diǎn)是D，則第一個(gè)滿足是其father左兒子的節(jié)點(diǎn)是F，則C的father就是D的后繼，即F是D的后繼。

時(shí)間復(fù)雜度分析

不論往上找還是往下找，總共遍歷的節(jié)點(diǎn)數(shù)都不大于樹的高度。所以時(shí)間復(fù)雜度是 O(h)，其中 h 是樹的高度。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode *father;*     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}* };*/
class Solution{
public:TreeNode* inorderSuccessor(TreeNode* p) {if (p->right) {p = p->right;  //易錯(cuò)帶while (p->left) p = p->left;return p;}//p == p->father->right 用來判斷p是否是右節(jié)點(diǎn)while (p->father && p == p->father->right) p = p->father;return p->father;}
};

3.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

題目

題解

(棧，隊(duì)列) O(n)

這是一道基礎(chǔ)題，只要把功能實(shí)現(xiàn)對就可以，不需要考慮運(yùn)行效率。

我們用兩個(gè)棧來做，一個(gè)主棧，用來存儲數(shù)據(jù)；一個(gè)輔助棧，用來當(dāng)緩存。

棧：先進(jìn)后出，隊(duì)列：先進(jìn)先出

• push(x)，我們直接將 x 插入主棧中即可。
• pop()，此時(shí)我們需要彈出最先進(jìn)入棧的元素，也就是棧底元素。我們可以先將所有元素從主棧中彈出，壓入輔助棧中。則輔助棧的棧頂元素就是我們要彈出的元素，將其彈出即可。然后再將輔助棧中的元素全部彈出，壓入主棧中。
• peek()，可以用和pop()操作類似的方式，得到最先壓入棧的元素。
• empty()，直接判斷主棧是否為空即可。

時(shí)間復(fù)雜度分析

• push()：O(1)；
• pop(): 每次需要將主棧元素全部彈出，再壓入，所以需要 O(n) 的時(shí)間；
• peek()：類似于pop()，需要 O(n) 的時(shí)間；
• empty()：O(1)；

class MyQueue {
public:/** Initialize your data structure here. */stack<int> stk, cache;MyQueue() {  //初始化，如果棧不為空，則用while()清空while (!stk.empty()) {stk.pop();}while (!cache.empty()) {cache.pop();}}/** Push element x to the back of queue. */void push(int x) {stk.push(x);}void copy(stack<int>& a, stack<int>& b) {while (a.size()) {b.push(a.top());a.pop();}}/** Removes the element from in front of queue and returns that element. */int pop() {if (stk.empty()) return -1;  //如果棧為空，返回-1copy(stk, cache);int res = cache.top();cache.pop();copy(cache, stk);return res;}/** Get the front element. */int peek() {if (stk.empty()) return NULL;  //如果棧為空，返回NULLcopy(stk, cache);int res = cache.top();copy(cache, stk);return res;}/** Returns whether the queue is empty. */bool empty() {return stk.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* bool param_4 = obj.empty();*/