1.重建二叉樹

題目

題解

(遞歸) O(n)

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

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

具體步驟如下：

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

時間復雜度分析

我們在初始化時，用哈希表(unordered_map<int,int>)記錄每個值在中序遍歷中的位置，這樣我們在遞歸到每個節(jié)點時，在中序遍歷中查找根節(jié)點位置的操作，只需要 O(1) 的時間。此時，創(chuàng)建每個節(jié)點需要的時間是 O(1)，所以總時間復雜度是 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;  //用哈希表記錄每個值在中序遍歷中的位置 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é)點在中序遍歷中是在第幾個位置TreeNode* root = new TreeNode(pre[pl]); //生成新的根節(jié)點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.二叉樹的下一個節(jié)點

題目

題解

(模擬) O(h)

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

中序遍歷（左 根 右）

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

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

時間復雜度分析

不論往上找還是往下找，總共遍歷的節(jié)點數(shù)都不大于樹的高度。所以時間復雜度是 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;  //易錯帶while (p->left) p = p->left;return p;}//p == p->father->right 用來判斷p是否是右節(jié)點while (p->father && p == p->father->right) p = p->father;return p->father;}
};

3.用兩個棧實現(xiàn)隊列

題目

題解

(棧，隊列) O(n)

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

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

棧：先進后出，隊列：先進先出

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

時間復雜度分析

• push()：O(1)；
• pop(): 每次需要將主棧元素全部彈出，再壓入，所以需要 O(n) 的時間；
• peek()：類似于pop()，需要 O(n) 的時間；
• 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();*/