C++進階—二叉樹進階

第一章：內容安排說明

map和set特性需要先鋪墊二叉搜索樹，而二叉搜索樹也是一種樹形結構
二叉搜索樹的特性了解，有助于更好的理解map和set的特性
二叉樹中部分面試題稍微有點難度，在前面講解大家不容易接受，且時間長容易忘
有些OJ題使用C語言方式實現比較麻煩，比如有些地方要返回動態開辟的二維數組，非常麻煩。

第二章：二叉搜索樹

2.1 二叉搜索樹概念

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:

若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
它的左右子樹也分別為二叉搜索樹

2.2 二叉搜索樹操作

1. 二叉搜索樹的查找

a、從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。
b、最多查找高度次，走到到空，還沒找到，這個值不存在。

2. 二叉搜索樹的插入

a. 樹為空，則直接新增節點，賦值給root指針
b. 樹不空，按二叉搜索樹性質查找插入位置，插入新節點

3. 二叉搜索樹的刪除

首先查找元素是否在二叉搜索樹中，如果不存在，則返回, 否則要刪除的結點可能分下面四種情況：
?a. 要刪除的結點無孩子結點
?b. 要刪除的結點只有左孩子結點
?c. 要刪除的結點只有右孩子結點
?d. 要刪除的結點有左、右孩子結點

看起來有待刪除節點有4中情況，實際情況a可以與情況b或者c合并起來，因此真正的刪除過程如下：

情況b：刪除該結點且使被刪除節點的雙親結點指向被刪除節點的左孩子結點--直接刪除
情況c：刪除該結點且使被刪除節點的雙親結點指向被刪除結點的右孩子結點--直接刪除
情況d：在它的右子樹中尋找中序下的第一個結點(關鍵碼最小)，用它的值填補到被刪除節點中，再來處理該結點的刪除問題--替換法刪除

2.3 二叉搜索樹的實現

template <class K> //因為鍵值參與比較，所以改名為K(Key)
struct BSTreeNode { //數組只適合表示完全二叉樹BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key): _left(nullptr), _right(nullptr), _key(key) {}
};template <class K>
class BSTree {typedef BSTreeNode<K> Node;
public://bool Insert(const K& key) {//	if (_root == nullptr) {//		_root = new Node(key);//		return true;//	}//	//不為空找插入位置//	//比當前根節點小，走左邊；比當前根節點大，走右邊。直到節點為空//	Node* cur = _root;//	while (cur) {//		if (key > cur->_key) //比當前根節點大，走右邊。//			cur = cur->_right;//		else if (key < cur->_key) //比當前根節點小，走左邊//			cur = cur->_left;//		else//			return false; //默認二叉搜索樹不允許重復值//	}//	cur = new Node(key);//	//這里雖然new了節點，但并未鏈接。//	//二叉樹的鏈接是要父節點指向子節點。//	return true;//}//為了解決上述問題還需要一個父節點指針，//cur往后遍歷之前，父節點指向cur節點bool Insert(const K& key) {if (_root == nullptr) {_root = new Node(key);return true;}//不為空找插入位置//比當前根節點小，走左邊；比當前根節點大，走右邊。直到節點為空Node* parent = nullptr;Node* cur = _root;while (cur) {parent = cur; //cur往后遍歷之前，父節點指向cur節點if (key > cur->_key) //比當前根節點大，走右邊。cur = cur->_right;else if (key < cur->_key) //比當前根節點小，走左邊cur = cur->_left;elsereturn false; //默認二叉搜索樹不允許重復值}cur = new Node(key);//這里雖然new了節點，但并未鏈接。//二叉樹的鏈接是要父節點指向子節點。//但鏈接在左或右不知道，所以需要比較if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;return true;}bool Find(const K& key) {Node* cur = _root;while (cur) {if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;elsereturn true;}return false;}bool Erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur) {if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else { //到這，cur指向被刪除的節點if (cur->_left == nullptr) { //1.被刪除節點的左子節點為空，即只有右子節點if (cur == _root) //還需要考慮被刪除節點是根節點的情況_root = cur->_right;else {if (cur == parent->_left) //且被刪除節點是其父節點的左子節點parent->_left = cur->_right;else //被刪除節點是其父節點的右子節點parent->_right = cur->_right;}}else if (cur->_right == nullptr) { //2.被刪除節點的右子節點為空，即只有左子節點if (cur == _root)_root = cur->_left;else {if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;}}else { //3.左右都不為空//右樹的最小節點(最左節點)//不能用遞歸或上方Find函數找到要刪除的節點，//因為下方交換了兩個節點后，現在已經不是二叉搜索樹，//所以還需要最左節點的父節點。//如果右樹的最左節點就是cur->_right，且parent初始化為空，//那么循環就不會進，導致parent為空(無法鏈接)，所以要將parent賦值為cur//parent = nullptr;parent = cur;Node* subLeft = cur->_right;//將被刪除節點的右子節點作為起點while (subLeft->_left) { //找到最左下角的節點parent = subLeft;subLeft = subLeft->_left;}swap(cur->_key, subLeft->_key);//交換最左節點和被刪除節點//雖然上方循環一直在找最左節點，但最左節點并不一定是其父節點的左子節點。//假設一種情況，(只描述樹的一部分)，一棵樹只有右子樹，//且根節點的右子節點也只有右子樹，要刪除的是根節點，這時的最左節點是根的右子節點。//所以需要判斷最左節點是其父節點的哪邊if (subLeft == parent->_left)parent->_left = subLeft->_right;elseparent->_right = subLeft->_right;}return true;}}return false;}//這種方式會導致在類外調用時找不到根節點//bt.InOrder();//調用中序遍歷需要根節點，但不知道根節點是誰//void InOrder(Node* root) {//	if (root == nullptr)//		return;//	InOrder(root->_left);//	cour << root->_key << " ";//	InOrder(root->_right);//}void InOrder() {_InOrder(_root);cout << endl;}bool FindR(const K& key) { return _FindR(_root, key); }bool InsertR(const K& key) { return _InsertR(_root, key); }bool EraseR(const K& key) { return _EraseR(_root, key); }//BSTree() = default;//強制生成默認BSTree() {} //有缺省值初始化~BSTree() { //通過后序遞歸釋放數，當不能遞歸析構函數Destroy(_root);}//拷貝構造同樣是遞歸實現。以根、左子樹、右子樹的順序拷貝。//對于其左右子樹同樣可以以相同方法實現。BSTree(const BSTree<K>& t) {_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t) {swap(_root, t._root);return *this;}
private:Node* _root = nullptr;//類里面可以獲取根節點，所以在套一層，方便外面調用InOrder()void _InOrder(Node* root) {if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}bool _FindR(Node* root, const K& key) {if (root == nullptr)return false;if (key > root->_key)_FindR(root->_right, key);else if (key < root->_key)_FindR(root->_left, key);elsereturn true;}//bool _InsertR(Node* root, const K& key) { //這種方式雖然插入了節點，但沒有鏈接//在遞歸中，每次遞歸調用都會創建新的棧幀，//每個棧幀中的引用參數都是獨立的，可以綁定到不同的變量。bool _InsertR(Node*& root, const K& key) {if (root == nullptr) {root = new Node(key);return true;}//當遞歸進行到上面這個條件時，當前這一層的遞歸是//_InsertR(root->_right, key);或_InsertR(root->_left, key);//也就是說，上一層的root->_left或root->_right引用了這層的root//在root這里創建節點自然就被鏈接上了。if (key > root->_key)return _InsertR(root->_right, key);else if (key < root->_key)return _InsertR(root->_left, key);elsereturn false;}//這里的引用與插入類似，刪除需要被刪除節點的父節點，引用恰好能實現bool _EraseR(Node*& root, const K& key) {if (root == nullptr)return false;if (key > root->_key)return _EraseR(root->_right, key);else if (key < root->_key)return _EraseR(root->_left, key);else {//這里root指向的是被刪除的節點，//同時，當前這一層的遞歸是_EraseR(root->_right, key);或_EraseR(root->_left, key);//也就是說，root上一層的root->_left或root->_right引用了這層的root。if (root->_left == nullptr) {Node* del = root;//記錄被刪除節點的指針//將root上一層的root->_left或root->_right指向了root下一層的_rightroot = root->_right;delete del;//如果刪除的是根節點也沒有問題，(走到這里時說明沒有左子樹)//因為root是根節點指針的引用，刪除根節點//也可以理解為將根節點指針移動到根的右子節點}else if (root->_right == nullptr) {Node* del = root;root = root->_left;delete del;}else {Node* subLeft = root->_right;while (subLeft->_left)subLeft = subLeft->_left;swap(root->_key, subLeft->_key);return _EraseR(root->_right, key);//不能再整棵樹中用遞歸解決，//因為交換了替換節點和被刪除節點就不在滿足二叉搜索樹的性質了//但可以在小范圍內使用遞歸(被刪除節點右子節點作為根的樹)，//被刪除節點的右子樹都比被刪除節點大，替換節點是該右子樹的最左節點(最小節點)，但依然比刪除節點大//被刪除節點與最左節點交換相當于換過來一個更小的值，依然能滿足二叉搜索樹的性質，即左子節點<根//當刪除的是根節點時，根節點被換到了其右子數的最左節點，再將此時根的右子節點當做樹的根來刪除，//此時邏輯就回到上面的if (root->_left == nullptr)或else if (root->_right == nullptr)//也就是說第一層的root->_right是第二層root的別名，//第二層的root又指向了第三層的root->_left或root->_right//即第一層的root->_right指向了第三層的root->_left或root->_right//既刪除了根節點又完成鏈接}return true;}}//void Destroy(Node* root) { //該方式導致root置空無效，形參的改變不影響實參void Destroy(Node*& root) { //改為引用if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}Node* Copy(Node* root) {if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}
};

2.4 二叉搜索樹的應用

1. K模型：K模型即只有key作為關鍵碼，結構中只需要存儲Key即可，關鍵碼即為需要搜索到的值。

比如：給一個單詞word，判斷該單詞是否拼寫正確，具體方式如下：

以詞庫中所有單詞集合中的每個單詞作為key，構建一棵二叉搜索樹
在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。

2. KV模型：每一個關鍵碼key，都有與之對應的值Value，即<Key, Value>的鍵值對。該種方式在現實生活中非常常見：

比如英漢詞典就是英文與中文的對應關系，通過英文可以快速找到與其對應的中文，英文單詞與其對應的中文<word, chinese>就構成一種鍵值對；
再比如統計單詞次數，統計成功后，給定單詞就可快速找到其出現的次數，單詞與其出現次數就是<word, count>就構成一種鍵值對。

改造二叉搜索樹為KV結構

template <class K, class V>
struct BSTreeNode { //數組只適合表示完全二叉樹BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value): _left(nullptr), _right(nullptr), _key(key), _value(value) {}
};template <class K, class V>
class BSTree {typedef BSTreeNode<K, V> Node;
public:bool Insert(const K& key, const V& value) {if (_root == nullptr) {_root = new Node(key, value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur) {parent = cur; //cur往后遍歷之前，父節點指向cur節點if (key > cur->_key) //比當前根節點大，走右邊。cur = cur->_right;else if (key < cur->_key) //比當前根節點小，走左邊cur = cur->_left;elsereturn false; //默認二叉搜索樹不允許重復值}cur = new Node(key, value);if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;return true;}Node* Find(const K& key) { //通過key找valueNode* cur = _root;while (cur) {if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;elsereturn cur;}return nullptr;}bool Erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur) {if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else { //到這，cur指向被刪除的節點if (cur->_left == nullptr) { //1.被刪除節點的左子節點為空，即只有右子節點if (cur == _root) //還需要考慮被刪除節點是根節點的情況_root = cur->_right;else {if (cur == parent->_left) //且被刪除節點是其父節點的左子節點parent->_left = cur->_right;else //被刪除節點是其父節點的右子節點parent->_right = cur->_right;}}else if (cur->_right == nullptr) { //2.被刪除節點的右子節點為空，即只有左子節點if (cur == _root)_root = cur->_left;else {if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;}}else { //3.左右都不為空parent = cur;Node* subLeft = cur->_right;while (subLeft->_left) {parent = subLeft;subLeft = subLeft->_left;}swap(cur->_key, subLeft->_key);if (subLeft == parent->_left)parent->_left = subLeft->_right;elseparent->_right = subLeft->_right;}return true;}}return false;}void InOrder() {_InOrder(_root);cout << endl;}private:Node* _root = nullptr;//類里面可以獲取根節點，所以在套一層，方便外面調用InOrder()void _InOrder(Node* root) {if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}
};

2.5 二叉搜索樹的性能分析

插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能。
對有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度的函數，即結點越深，則比較次數越多。

但對于同一個關鍵碼集合，如果各關鍵碼插入的次序不同，可能得到不同結構的二叉搜索樹：

最優情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數為：O(log?N)
最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其平均比較次數為：O(N)
問題：如果退化成單支樹，二叉搜索樹的性能就失去了。那能否進行改進，不論按照什么次序插入關鍵碼，二叉搜索樹的性能都能達到最優？那么我們后續章節學習的AVL樹和紅黑樹就可以上場了。?

第三章：二叉樹進階面試題

1. 二叉樹創建字符串。606. 根據二叉樹創建字符串 - 力扣（LeetCode）

class Solution {
public://右為空、左右為空可以省略括號//只要有任意子樹，左子樹的括號都要加。右子樹只有存在時才加。string tree2str(TreeNode* root) {string str;if (root == nullptr)return str;str += to_string(root->val);//如果左子樹或右子樹至少有一個存在，就必須處理左子樹（即使左子樹為空，也要加 ()）。//if ((root->left == nullptr && root->right) || root->left)if (root->left || root->right) {str += '(';str += tree2str(root->left);str += ')';}//只有右子樹存在時才處理，否則完全省略。if (root->right) {str += '(';str += tree2str(root->right);str += ')';}return str;}
};

2. 二叉樹的分層遍歷1。102. 二叉樹的層序遍歷 - 力扣（LeetCode）

class Solution {
public:// 數據結構選擇//隊列：用于按層級順序存儲待訪問的節點。//二維數組：存儲最終的層序遍歷結果，每一層的節點值用一個子數組保存。vector<vector<int>> levelOrder(TreeNode* root) {//初始化隊列：如果根節點 root 非空，將其加入隊列，//并初始化 levelSize = 1（表示第一層有 1 個節點）。queue<TreeNode*> q;int levelSize = 0;if (root) {q.push(root);levelSize = 1;}vector <vector<int>> vv;while (!q.empty()) { //檢查隊列是否為空，如果不空則繼續處理。vector<int> v;while (levelSize--) { //處理當前層的所有節點（levelSize 控制循環次數）//從隊列頭部取出節點，將其值存入當前層的子數組 v。TreeNode* front = q.front();v.push_back(front->val);q.pop();//將該節點的左右子節點（如果存在）加入隊列（即下一層的節點）。if (front->left) q.push(front->left);if (front->right) q.push(front->right);}  levelSize = q.size();//更新 levelSize 為當前隊列大小（即下一層的節點數）。vv.push_back(v);}return vv;}
};

3.?二叉樹的分層遍歷2?107. 二叉樹的層序遍歷 II - 力扣（LeetCode）

class Solution {
public://從vector<vector<int>> vv結果來看，從最后一層進行層序遍歷//其實就是正向層序遍歷后再反轉vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;queue<TreeNode*> q;int levelSize = 0;if (root) {q.push(root);levelSize = 1;}while (!q.empty()) {vector<int> v;while (levelSize--) {TreeNode* front = q.front();q.pop();v.push_back(front->val);if (front->left) q.push(front->left);               if (front->right) q.push(front->right);         }vv.push_back(v);levelSize = q.size();}reverse(vv.begin(), vv.end());return vv;}
};

4. 給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。236. 二叉樹的最近公共祖先 - 力扣（LeetCode）

class Solution {
public://方法一：效率低//判斷節點 x 是否在以 root 為根的子樹中。//為下面 判斷p、q是否在當前節點的左右子樹 準備bool isTree(TreeNode* root, TreeNode* x) {if (root == nullptr) return false;if (root == x) return true;return isTree(root->left, x) || isTree(root->right, x);}//1.p和q分別在左右，當前節點就是公共祖先//2.其中一個就是當前樹的根// 1.首先檢查當前節點是否是p或q中的一個，如果是，直接返回當前節點// 2.然后檢查p和q分別位于當前節點的左子樹還是右子樹// 3.根據p和q的位置關系：// 如果一個在左，一個在右，當前節點就是LCA// 如果都在左，遞歸處理左子樹// 如果都在右，遞歸處理右子樹TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == p || root == q) //當前root是p或q，說明它是自身的祖先return root;bool pInLeft = isTree(root->left, p);//p是否在當前root的左子樹bool pInRight = !pInLeft;//p不在左子樹則一定在右子樹bool qInLeft = isTree(root->left, q);bool qInRight = !qInLeft;//一個在左，一個在右if ((pInLeft && qInRight) || (pInRight && qInLeft))return root;//都在左if (pInLeft && qInLeft)return lowestCommonAncestor(root->left, p, q);//都在右if (pInRight && qInRight)return lowestCommonAncestor(root->right, p, q);return nullptr;//其他情況（理論上不會走到這里，因為題目保證p和q在樹中）}//方法二//分別找出p和q的路徑，在找出相交節點//從根節點開始找，每遇到一個節點入棧，期間如果遇到葉子節點還不是，//那么將該節點出棧(因為這條路徑找不到)。直到找到目標節點。//分別找到從根節點到 p 和 q 的路徑（用棧存儲）。bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path) {if (root == nullptr) return false;//空樹或當前節點為空path.push(root);//當前節點入棧if (root == x) return true;//如果當前節點是目標節點返回真//遞歸在左、右子樹中查找if (FindPath(root->left, x, path)) return true;if (FindPath(root->right, x, path)) return true;path.pop(); //左右子樹都沒找到，當前節點不在路徑中，彈出return false;}//比較兩條路徑，找到最近公共祖先。TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pPath, qPath;//找到根到p、q的路徑。//其實這里只需要棧里的路徑，所以不需要接收返回值FindPath(root, p, pPath);FindPath(root, q, qPath);//讓兩條路徑長度一致（從底部對齊）//因為最近公共祖先的深度一定 ≤ min(p深度, q深度)，//且棧頂是最深節點while (pPath.size() != qPath.size()) {if (pPath.size() > qPath.size())//長的路徑彈出多余節點pPath.pop();elseqPath.pop();}//從后向前找最后一個相同的節點while (pPath.top() != qPath.top()) {pPath.pop();qPath.pop();}return pPath.top();}
};

5. 二叉樹搜索樹轉換成排序雙向鏈表。二叉搜索樹與雙向鏈表_牛客題霸_牛客網

class Solution {public://中序遍歷每個節點。創建prev和cur兩個指針//初始時prev指向空，cur指向中序遍歷第一個節點//每次都是prev的右指向cur，cur的左指向prev//假設中序遍歷結果是：4 6 8 10 12 14 16//如果 prev 不使用引用，而是值傳遞，那么每次遞歸調用時，//prev 的修改只會影響當前函數的副本，不會傳遞回上一層遞歸。//prev的第一次修改是在最深層的遞歸//當處理節點4時，prev初始為nullptr。//處理完4后，prev更新為4（但因為是值傳遞，外層的prev仍然是nullptr）。//接下來處理6時，prev仍然是nullptr，導致6的左指針無法正確指向4。//二叉搜索樹的中序遍歷結果是一個有序的序列。//利用中序遍歷的順序，將每個節點的left指向前驅節點，right指向后繼節點，void InorderConvert(TreeNode* cur, TreeNode*& prev) { //prev需要引用才能鏈接if (cur == nullptr) return;InorderConvert(cur->left, prev);cur->left = prev;if (prev) prev->right = cur;//cur指向第一個節點時，prev為空，解引用報錯，要注意。prev = cur;InorderConvert(cur->right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* cur = pRootOfTree, *prev = nullptr;InorderConvert(cur, prev);//轉換后pRootOfTree的最左依然是頭TreeNode* head = pRootOfTree;while (head && head->left)//找最左head = head->left;return head;}
};

6. 根據一棵樹的前序遍歷與中序遍歷構造二叉樹。105. 從前序與中序遍歷序列構造二叉樹 - 力扣（LeetCode）

class Solution {
public://前序確定根，中序確定左右子樹TreeNode* _build(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend) {//中序數組是用來確定左右子樹//當前子樹在中序數組中對應的區間為空，因此沒有節點屬于該子樹。if (inbegin > inend) return nullptr;//在中序數組中查找當前根節點的位置。//前序遍歷的第一個節點 preorder[prei] 是當前子樹的根節點。//在中序數組內查找該根節點的位置rooti。從而劃分其左右子樹區間int rooti = inbegin;while (rooti <= inend) {if (inorder[rooti] == preorder[prei])break;rooti++;}TreeNode* root = new TreeNode(preorder[prei++]);//[inbegin, rooti - 1] rooti [rooti + 1, inend]root->left = _build(preorder, inorder, prei, inbegin, rooti - 1);root->right = _build(preorder, inorder, prei, rooti + 1, inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;//prei 前序數組下標//prei：前序遍歷的當前索引（引用傳遞，確保遞歸中能正確更新）。//inbegin：當前子樹在中序遍歷中的起始位置。//inend：當前子樹在中序遍歷中的結束位置。TreeNode* root = _build(preorder, inorder, i, 0, inorder.size() - 1);return root;}
};

7.?根據一棵樹的中序遍歷與后序遍歷構造二叉樹?106. 從中序與后序遍歷序列構造二叉樹 - 力扣（LeetCode）

class Solution {
public:TreeNode* _build(vector<int>& inorder, vector<int>& postorder, int& posi, int inbegin, int inend) {if (inbegin > inend) return nullptr;int rooti = inbegin;while (rooti <= inend) {if (postorder[posi] == inorder[rooti])break;++rooti;}TreeNode* root = new TreeNode(postorder[posi--]);//后序遍歷的順序是 左子樹 → 右子樹 → 根，所以在處理后序數組時：//應該先構建右子樹，再構建左子樹（因為后序數組的最后一個元素是根，倒數第二個是右子樹的根，然后是左子樹的根）。//先遞歸右子樹，再遞歸左子樹（因為后序數組的右子樹根在左子樹根之前）。root->right = _build(inorder, postorder, posi, rooti + 1, inend);root->left = _build(inorder, postorder, posi, inbegin, rooti - 1);          return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i = postorder.size() - 1;TreeNode* root = _build(inorder, postorder, i, 0, inorder.size() - 1);return root;}
};

8.?二叉樹的前序遍歷，非遞歸迭代實現。144. 二叉樹的前序遍歷 - 力扣（LeetCode）

class Solution {
public://1.先訪問包括當前根的左路節點//2.在訪問每個左路節點的右子樹//重復上述兩個步驟vector<int> preorderTraversal(TreeNode* root) {  //用棧存儲左路節點//根據前序遍歷的順序，要先訪問最后的左路節點的右子樹stack<TreeNode*> s;vector<int> v;//存儲前序遍歷每個節點的值TreeNode* cur = root;while (cur || !s.empty()) {//將cur指向節點當做根，訪問該條左路節點while (cur) {v.push_back(cur->val);s.push(cur);cur = cur->left;}//訪問左路節點的右子樹TreeNode* top = s.top();s.pop();cur = top->right;}return v;}
};

9.?二叉樹中序遍歷，非遞歸迭代實現。94. 二叉樹的中序遍歷 - 力扣（LeetCode）

class Solution {
public://思路和前序遍歷類似，只是最先訪問的是左路節點的最后節點vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> v;TreeNode* cur = root;while (cur || !s.empty()) {//一路向左深入，入棧while (cur) {s.push(cur);cur = cur->left;}// "訪問完最左節點后訪問根節點"這一關鍵步驟在代碼中看起來不太直觀。// 中序遍歷的順序：左子樹 -> 根節點 -> 右子樹// 沿著左子樹一直向下，把經過的每個節點壓入棧中，// 這些被壓入的節點實際上都是"未來的根節點"。// 如果沒有左了，那么棧里面的就是根，所以去棧頂訪問根TreeNode* top = s.top();s.pop();v.push_back(top->val);cur = top->right;}return v;}
};

10.?二叉樹的后序遍歷，非遞歸迭代實現?145. 二叉樹的后序遍歷 - 力扣（LeetCode）

class Solution {
public://思路和前序中序有相似之處//沿著左子樹一直向下，將經過的節點全部壓棧，查看棧頂節點，判斷是否可訪問當前節點//因為后序遍歷是左、右、根，如果它的右為空可以訪問，右不為空，繼續走右子樹。//此時出現一個問題，不知道該節點應該何時訪問，因為在訪問它的右子樹之前已經訪問過它。//根據后序遍歷順序，當該節點的右子樹已訪問完時，前一個節點一定是它的右子節點。//所以需要一個prev指針記錄。  vector<int> postorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> s;TreeNode* cur = root;TreeNode* prev = nullptr;//記錄前一個訪問的節點while (cur || !s.empty()) {while (cur) {s.push(cur);cur = cur->left;}TreeNode* top = s.top();//查看棧頂節點//當前節點沒有右子樹 或 當前節點的右子樹已經訪問過if (top->right == nullptr || top->right == prev) { //判斷是否可訪問當前節點s.pop();v.push_back(top->val);prev = top;//記錄最后一個被彈出棧并訪問的節點}elsecur = top->right;//處理右子樹}return v;}
};

作業

1. 將整數序列（7-2-4-6-3-1-5）按所示順序構建一棵二叉排序樹a（亦稱二叉搜索樹），之后將整數8按照二叉排序樹規則插入樹a中，請問插入之后的樹a中序遍歷結果是（）?

A.1-2-3-4-5-6-7-8
B.7-2-1-4-3-6-5-8
C.1-3-5-2-4-6-7-8
D.1-3-5-6-4-2-8-7
E.7-2-8-1-4-3-6-5
F.5-6-3-4-1-2-7-8

答案：A
插入之后的樹仍舊是二叉搜索樹，因此只要是有序的結果則正確，而有序的結果只有A
因此：選擇A

2. 下面關于二叉搜索樹正確的說法是（）

A.待刪除節點有左子樹和右子樹時，只能使用左子樹的最大值節點替換待刪除節點
B.給定一棵二叉搜索樹的前序和中序遍率歷結果，無法確定這棵二叉搜索樹
C.給定一棵二叉搜索樹，根據節點值大小排序所需時間復雜度是線性的
D.給定一棵二叉搜索樹，可以在線性時間復雜度內轉化為平衡二叉搜索樹

答案：C
?A：錯誤，當待刪除節點的左右子樹均存在時，既可以在左子樹中找一個最大的節點作為替代節點，也可以在右子樹中找一個最小的節點作為替代節點，左右子樹中都可以找替代節點
B：錯誤，根據前序遍歷和中序遍歷，是可以確定一棵樹的結構，使用兩個遍歷結果確定樹的結構，其中有一個遍歷結果必須要是中序遍歷結果。
C：正確，二叉搜索樹遍歷一遍，就可以得到一個有序序列，因此，時間復雜度為O(N)
D：錯誤，這里面還需要牽扯到旋轉等其他操作，時間復雜度不是線性的
因此：選擇C

3. 下面的哪個序列可能是二叉搜索樹中序遍歷的結果? （）

A.73 8 2 9 4 11
B. 2 3 4 7 8 9 11
C.11 2 9 3 8 4 7
D.以上均可

答案：B
二叉搜索樹的特性：如果對二叉搜索樹進行中序遍歷，可以得到有序的序列
因此：選擇B

4. 關于二叉搜索樹特性說法錯誤的是（）

A.二叉搜索樹最左側的節點一定是最小的
B.二叉搜索樹最右側的節點一定是最大的
C.對二叉搜索樹進行中序遍歷，一定能夠得到一個有序序列
D.二叉搜索樹的查找效率為O(log_2N)

答案：D
二叉搜索樹的概念：
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹：
1. 若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
2. 若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
3. 它的左右子樹也分別為二叉搜索樹
從概念中可以得出以下性質：
1. 二叉搜索樹中最左側節點一定是最小的，最右側節點一定是最大的
2. 對二叉搜索樹進行中序遍歷，可以得到一個有序的序列
A：正確
B：正確
C：正確
D：錯誤，二叉搜索樹最差情況下會退化為單支樹，因此：其查找的效率為O(N)
因此：選擇D