目錄

• 棧與隊列
• • 棧用于匹配的問題
  • 隊列用于堆
• 二叉樹系列
• • 深度遍歷，遞歸與迭代
  • 層序遍歷
  • 二叉樹屬性
  • 二叉樹修改與構造
  • 二叉搜索樹
  • 公共祖先
  • 二叉搜索樹的修改與構造

棧與隊列

棧用于匹配的問題

20. 有效的括號
https://leetcode-cn.com/problems/valid-parentheses/
不匹配的三種情況;
1、字符串左方向的括號多余了
2、字符串右方向的括號多余了
3、字符串括號沒有多余，但是類型不匹配。
使用棧的時候三者對應到的棧的情況;
1、已經遍歷完字符串，但是棧不為空
2、遍歷字符串匹配的過程中，棧已經為空了
3、再遍歷字符串匹配的過程中，發現棧中沒有要匹配的字符。

class Solution {
public:bool isValid(string s) {stack<int> st;for(int i = 0; i < s.size(); i++){if(s[i] == '(') st.push(')');else if(s[i] == '[') st.push(']');else if(s[i] == '{') st.push('}');//接下來就是判斷,這個是1、3情況else if(st.empty() || st.top() != s[i]){return false;}//如果匹配，那么出棧else{st.pop();}}//第2種情況，遍歷完字符串，棧不為空return st.empty();}
};

1047. 刪除字符串中的所有相鄰重復項,與上一題思路一致，注意reverse函數的使用。
https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/

class Solution {
public:string removeDuplicates(string s) {stack<char> st;for(int i = 0; i < s.size(); i++){if(!st.empty() && st.top() == s[i]){st.pop();}elsest.push(s[i]);}string result ="";//將stack中數據輸出while(!st.empty()){result += st.top();st.pop();} //然后倒序reverse(result.begin(),result.end());return result;}
};

150. 逆波蘭表達式求值，做計算器程序的肯定知道這個，不過一般來說我們編寫的是將中綴表達式轉換為逆波蘭表達式。
逆波蘭表達式適合用棧操作運算：遇到數字則入棧；遇到算符則取出棧頂兩個數字進行計算，并將結果壓入棧中。
與前幾題一樣思路，先將stirng轉換成int入棧，tokens[i]是運算符，使用該運算符計算棧頂前兩個元素。
需要注意的編程細節:
1、stack.pop()并不返回棧頂元素。所以要在pop之前，取top元素。
2、 stoi(s1)可以將string類型數據轉化為int類型，比較方便。

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for(int i = 0; i < tokens.size(); i++){if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){int num2 = st.top();st.pop();int num1 = st.top();st.pop();if(tokens[i] == "+"){st.push(num1 + num2);}else if(tokens[i] == "-"){st.push(num1 - num2);}else if(tokens[i] == "*"){st.push(num1 * num2);}else{st.push(num1 / num2);}}else{st.push(stoi(tokens[i]));}}return st.top();}
};

隊列用于堆

347. 前 K 個高頻元素，思路簡單，對容器的使用比較復雜。
1、統計元素出現頻率，使用map
2、對頻率進行排序，使用優先級隊列（從隊頭取元素，從隊尾添加元素，隊列內部自動按照元素的權值排序）
3、找出前K個高頻元素，使用小頂堆，小頂堆每次將最小的元素彈出，最后小頂堆中積累的才是K個最大元素。
構建過程：
1、根據頻率，構建map
2、構建小頂堆，將所有頻率送入堆中，如果堆的大小大于K了，將元素從堆頂彈出。
這里需要注意priority_queue的設置方式:

priority_queue<Type, Container(Type), Functional>

Type 就是數據類型，Container 就是容器類型（Container必須是用數組實現的容器，比如vector,deque等等，但不能用 list。STL里面默認用的是vector），Functional 就是比較的方式，當需要用自定義的數據類型時才需要傳入這三個參數，使用基本數據類型時，只需要傳入數據類型，默認是大頂堆.
這里我們設置成這樣:
送入的是pair對（這里指map），比較方式需要自定義，這里比較的是pair對第二個元素的值，從小到大排序。（注意優先隊列以vector為容器，隊首指向vector后面，隊尾指向vector前面）

 priority_queue< pair<int,int>,vector< pair<int,int> >,mycomparison > pri_que;

class Solution {
public://定義優先隊列的排序方式,根據pair的第二個元素的大小，大的排后面。class mycomparison {public:bool operator()(const pair<int,int>& lhs,const pair<int,int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {//統計元素出現頻率unordered_map<int,int> map; //map<nums[i],對應頻次>for(int i = 0; i < nums.size(); i++)map[nums[i]]++;//對頻率排序//定義一個小頂堆，大小為kpriority_queue< pair<int,int>,vector< pair<int,int> >,mycomparison > pri_que;//用固定大小k的小頂堆掃描所有頻率的數值for(unordered_map<int,int>::iterator it = map.begin(); it != map.end(); it++){pri_que.push(*it);if(pri_que.size() > k) pri_que.pop();}//找出前k個高頻元素，因為小頂堆先彈出的是最小的，所以倒序輸出到數組中。vector<int> result(k);for(int i = k - 1; i >= 0; i--){result[i] = pri_que.top().first;pri_que.pop();}return result;}
};

二叉樹系列

二叉樹鏈式存儲方式：

struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

深度遍歷，遞歸與迭代

三種遍歷方式:
144. 二叉樹的前序遍歷
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
145. 二叉樹的后序遍歷
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
94. 二叉樹的中序遍歷
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

遞歸法模板：前序遍歷為例

class Solution {
public:void traversal(TreeNode* cur,vector<int>& vec){if(cur == nullptr) return;vec.push_back(cur->val);traversal(cur->left,vec);traversal(cur->right,vec);}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};

迭代法模板：中序遍歷為例
注意：棧的特性入棧和出棧相反，所以如果想輸出順序為“左中右”，入棧順序必須為“右中左”

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root != nullptr) st.push(root);while(!st.empty()){TreeNode* node = st.top();if(node != nullptr){st.pop();if(node->right != nullptr) st.push(node->right);st.push(node);st.push(nullptr);if(node->left != nullptr) st.push(node->left);}else{st.pop();result.push_back(st.top()->val);st.pop();}}return result;}
};

層序遍歷

層序遍歷模板如下:

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if(root != nullptr) que.push(root);vector<vector<int>> result;while(!que.empty()) {int size = que.size();vector<int> vec;for(int i = 0; i < size; i++){TreeNode* node = que.front();que.pop();vec.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(vec);}return result;}
};

102. 二叉樹的層序遍歷
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
107. 二叉樹的層序遍歷 II
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
199. 二叉樹的右視圖
https://leetcode-cn.com/problems/binary-tree-right-side-view/
637. 二叉樹的層平均值
https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
429. N 叉樹的層序遍歷
https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
515. 在每個樹行中找最大值，注意max初始值取最小值INT_MIN
https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
116. 填充每個節點的下一個右側節點指針,這一題要注意同層節點之間的鏈接，在單層遍歷的時候記錄本層的頭部節點，然后在遍歷的時候讓前一個節點指向本節點，本層最后一個節點next指向nullptr。
117. 填充每個節點的下一個右側節點指針 II，這兩題代碼一樣。
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if(root != nullptr) que.push(root);while(!que.empty()){int size = que.size();Node* pre;Node* now;for(int i = 0; i < size; i++){//每層第一個元素if(i == 0){pre = que.front();que.pop();now = pre;}else    //非第一個元素{now = que.front();que.pop();pre->next = now;pre = now;}if(now->left) que.push(now->left);if(now->right) que.push(now->right);}//每一層最后一個元素pre->next = nullptr;}return root;}
};

104. 二叉樹的最大深度，層序遍歷,在while循環中++；
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
111. 二叉樹的最小深度,一樣的思路，不過在每層節點遍歷時需要檢查是否無左右孩子，如果沒有，則立刻返回當前層數。

if(!node->left && !node->right) return result;

二叉樹屬性

101. 對稱二叉樹
https://leetcode-cn.com/problems/symmetric-tree/
遞歸法：外層是對稱的，內層也是對稱的。
確定遞歸函數參數、返回值：

bool compare(TreeNode* left,TreeNode* right)

確定終止條件：
1、左右都為空，返回true
2、左右只有一個為空，返回false
3、左右結點均不為空，比較結點數值，不相同返回false
4、左右結點均不為空，數值相同時，還要繼續向下判斷
確定單層邏輯;
1、比較二叉樹外側是否對稱：傳入左結點的左孩子，右結點的右孩子。
2、比較內側是否對稱，傳入左結點的右孩子，右結點的左孩子。
3、如果左右都對稱就返回true，否則返回false

class Solution {
public:bool compare(TreeNode* left,TreeNode* right){if(!left && !right) return true;else if((!left && right) || (left && !right)) return false;else if(right->val != left->val) return false;//下面就是right->val == left->val的情況了，還得繼續探討bool outside = compare(right->right,left->left);bool inside = compare(right->left,left->right);return (outside && inside);}bool isSymmetric(TreeNode* root) {if(root == nullptr) return true;return compare(root->left,root->right);}
};

關于二叉樹的最小深度與最大深度，在層序遍歷中已經涉及到了
…在此省略
222. 完全二叉樹的節點個數,層序遍歷+節點計數
https://leetcode-cn.com/problems/count-complete-tree-nodes/
110. 平衡二叉樹
https://leetcode-cn.com/problems/balanced-binary-tree/
遞歸三部曲：
1、確定遞歸函數的參數和返回值
傳入當前節點，返回值為當前節點的高度。返回-1表示不是平衡二叉樹
2、終止條件
遇到空節點為終止，返回0，表示當前節點為根節點的高度為0
3、單層的邏輯
判斷當前傳入節點為根節點的二叉樹是否為平衡二叉樹：比較左子樹高度和右子樹高度，差值<=1返回當前二叉樹的高度，否則返回-1.

class Solution {
public:int getDepth(TreeNode* node){if(node == nullptr) return 0;int leftDepth = getDepth(node->left);if(leftDepth == -1) return -1;int rightDepth = getDepth(node->right);if(rightDepth == -1) return -1;int result;if(abs(leftDepth - rightDepth) > 1)return -1;elseresult = 1 + max(leftDepth,rightDepth);return result;}bool isBalanced(TreeNode* root) {if(getDepth(root) != -1) return true;else return false;}
};

257. 二叉樹的所有路徑
遞歸三部曲+前序遍歷+回溯pop+字符串處理即可。

class Solution {
public:void traversal(TreeNode* cur, vector<int>& path,vector<string>& result){path.push_back(cur->val);//到達葉子節點if(cur->left == nullptr && cur->right == nullptr){string sPath;for(int i = 0; i < path.size() - 1; i++){sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);return;}//如果不是葉子節點if(cur->left){traversal(cur->left,path,result);path.pop_back();    //回溯}if(cur->right){traversal(cur->right,path,result);path.pop_back();    //回溯}}vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if(root == nullptr) return result;traversal(root,path,result);return result;}
};

404. 左葉子之和
https://leetcode-cn.com/problems/sum-of-left-leaves/
如果某節點的左節點不為空，且左節點沒有左右孩子，那么這個節點就是左葉子。
必須通過節點的父節點來判斷其左孩子是不是左葉子。
遞歸三部曲：
1、返回值為數值之和，傳入參數為樹的根節點
2、終止條件：遇到空節點返回
3、單層邏輯：遇到左葉子節點的時候，記錄數值，然后通過遞歸求取左子樹左葉子之和和右子樹左子葉之和，相加便是整個樹的左葉子之和。

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(root == nullptr) return 0;int leftval = sumOfLeftLeaves(root->left);int rightval = sumOfLeftLeaves(root->right);int midval = 0;if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr){midval = root->left->val;}int sum = midval + leftval + rightval;return sum;}
};

513. 找樹左下角的值
https://leetcode-cn.com/problems/find-bottom-left-tree-value/
層序遍歷+記錄每一行的第一個節點數值即可。
112. 路徑總和
https://leetcode-cn.com/problems/path-sum/
遞歸三部曲：
1、參數：二叉樹的根節點+一個計數器
這個計數器用來計算二叉樹的一條邊之和是否正好是目標和，計數器為int
返回值：bool
2、終止條件
count初始值為目標和，然后每次減去遍歷路徑點的數值。
如果最后count == 0，同時到了葉子節點的話，說明找到了目標和。
3、單層邏輯
由于終止條件是判斷葉子節點，所以遞歸的過程中不要讓空節點進入遞歸。
如果遞歸函數的返回值為true，說明找到了合適的路徑，應該立即返回。

class Solution {
public:bool traversal(TreeNode* cur,int count){if(cur->left == nullptr && cur->right == nullptr && count == 0) return true;    //遇到葉子節點，并且計數為0if(cur->left == nullptr && cur->right == nullptr) return false;     //遇到葉子節點而沒有找到合適的邊，直接返回if(cur->left) {count -= cur->left->val;if(traversal(cur->left,count)) return true;count += cur->left->val;}if(cur->right) {count -= cur->right->val;if(traversal(cur->right,count)) return true;count += cur->right->val;}//否則return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root == nullptr) return false;targetSum = targetSum - root->val;return traversal(root,targetSum);}
};

二叉樹修改與構造

226. 翻轉二叉樹
先序遍歷，先交換左右孩子，然后反轉左子樹，反轉右子樹。

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root == nullptr) return root;swap(root->left,root->right);invertTree(root->left);invertTree(root->right);return root;}
};

106. 從中序與后序遍歷序列構造二叉樹 比較復雜
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
步驟：
1、如果數組大小為0的話，說明是空節點
2、如果不為空，取后序數組最后一個元素作為節點元素
3、找到后序數組最后一個元素在中序數組的位置，作為切割點
4、切割中序數組，切成中序左數組和中序右數組。（記住，先切割中序數組！！！）
5、切割后序數組，切成后序左數組和后序右數組
6、遞歸處理左區間和右區間

切割的時候按照左閉右開的原則。后序數組的切割要根據中序數組切割出來的大小，還要注意后序數組在切割前要將最后一個數剔除。

class Solution {
public:TreeNode* traversal(vector<int>& inorder,int Inbegin,int Inend,vector<int>& postorder,int Postbegin,int Postend){//第一步,檢查后序數組大小if(Postbegin == Postend) return nullptr;//第二步：后序數組中最后一個元素，就是當前的中間節點int rootval = postorder[Postend - 1];TreeNode* root = new TreeNode(rootval);//葉子節點if(Postbegin - Postend == 1) return root;//第三步，中序數組找切割點int splitIndex = 0;for(splitIndex = Inbegin; splitIndex < Inend; splitIndex++){if(inorder[splitIndex] == rootval) break;}//第四步，切割中序數組，得到中序左數組和中序右數組int leftInbegin = Inbegin;int leftInend = splitIndex;int rightInbegin = splitIndex+1;int rightInend = Inend;//第五步：切割后序數組，得到后序左數組和后序右數組int leftPostbegin = Postbegin;int leftPostend = Postbegin + leftInend - leftInbegin;int rightPostbegin = leftPostend;int rightPostend = Postend - 1;//第六步，遞歸處理左區間和右區間root->left = traversal(inorder,leftInbegin,leftInend,postorder,leftPostbegin,leftPostend);root->right = traversal(inorder,rightInbegin,rightInend,postorder,rightPostbegin,rightPostend);return root;} TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size() == 0 || postorder.size() == 0) return nullptr;//左閉右開return traversal(inorder,0,inorder.size(),postorder,0,postorder.size());}
};

105. 從前序與中序遍歷序列構造二叉樹,操作類似
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/
654. 最大二叉樹
https://leetcode-cn.com/problems/maximum-binary-tree/submissions/

二叉搜索樹

700. 二叉搜索樹中的搜索
遞歸：

    TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr || root->val == val) return root;if(root->val > val) return searchBST(root->left,val);if(root->val > val) return searchBST(root->right,val);return nullptr;}

98. 驗證二叉搜索樹
二叉搜索樹中序遍歷得到的數組是遞增的。

class Solution {
public:vector<int> vec;void traversal(TreeNode* node){if(node == nullptr) return ;traversal(node->left);vec.push_back(node->val);traversal(node->right);}bool isValidBST(TreeNode* root) {vec.clear();traversal(root);for(int i = 1; i < vec.size(); i++){if(vec[i] <= vec[i - 1]) return false;}return true;}
};

530. 二叉搜索樹的最小絕對差
轉換為有序數組，然后對有序數組進行比較。
501. 二叉搜索樹中的眾數
轉換為有序數組，然后對相鄰兩個元素進行比較，統計相同頻次，有一些細節需要注意。

class Solution {
public:vector<int> vec;void traversal(TreeNode* node){if(node == nullptr) return ;traversal(node->left);vec.push_back(node->val);traversal(node->right);}vector<int> findMode(TreeNode* root) {if(root == nullptr) return {};vec.clear();vector<int> result;traversal(root);unordered_map<int,int> umap;int maxcount = 1;int count = 1;result.push_back(vec[0]);for(int i = 1; i < vec.size(); i++){if(vec[i] == vec[i-1]){count++;}elsecount = 1;if(count == maxcount)result.push_back(vec[i]);if(count > maxcount){maxcount = count;result.clear();result.push_back(vec[i]);}}return result;}
};

538. 把二叉搜索樹轉換為累加樹
https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
定義一個全局變量preval用來存儲上一個節點值，然后右中左遍歷二叉樹。中間節點處理就是加上preaval，然后更新preval。

公共祖先

236. 二叉樹的最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
通過后序遍歷，回溯，自下向上。
如何判斷一個節點是節點q和節點p的公共祖先：
如果找到一個節點，發現左子樹出現了節點p，右子樹出現了q；或者左子樹出現q，右子樹出現p。那么該節點就是節點p和q的最近公共祖先。

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == p || root == q || root == nullptr) return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);//如果left和right都不為空，則說明root就是最近公共祖先if(left != nullptr && right != nullptr) return root;if(left == nullptr && right != nullptr) return right;else if(left != nullptr && right == nullptr) return left;else return nullptr;}
};

235. 二叉搜索樹的最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/submissions/

class Solution {
public:TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q){if(cur == nullptr) return cur;if(cur->val > p->val && cur->val > q->val) {TreeNode* left = traversal(cur->left,p,q);if(left != nullptr) return left;}if(cur->val < p->val && cur->val < q->val){TreeNode* right = traversal(cur->right,p,q);if(right != nullptr) return right;}//否則說明，cur是最近公共祖先（從底向上）return cur;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root,p,q);}
};

二叉搜索樹的修改與構造

701. 二叉搜索樹中的插入操作
https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
遍歷二叉搜索樹，然后遇到空節點，插入即可。遞歸函數返回節點。

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root == nullptr){//插入操作TreeNode* node = new TreeNode(val);return node;}if(root->val > val) root->left = insertIntoBST(root->left,val);if(root->val < val) root->right = insertIntoBST(root->right,val);return root; }
};

450. 刪除二叉搜索樹中的節點
https://leetcode-cn.com/problems/delete-node-in-a-bst/
刪除操作比較麻煩：
1、沒有找到刪除的結點，遍歷到空結點直接返回。
2、找到了刪除的結點：
【1】如果左右孩子都為空，直接刪除這個結點，返回NULL為根結點
【2】如果左孩子為空，右孩子不為空，刪除結點，右孩子補位，返回右孩子作為根結點
【3】如果右孩子為空，左孩子不為空，刪除結點，左孩子補位，返回左孩子作為根結點
【4】如果左右孩子不為空，則將刪除結點的左子樹的頭結點放到刪除結點的右子樹的最左邊結點的左孩子上，返回刪除結點右孩子，作為新的結點

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(root == nullptr) return root;//如果找到了該節點if(root->val == key) {//第二種情況，左右孩子均空，刪除該節點，返回nullptrif(root->right == nullptr && root->left == nullptr) return nullptr;if(root->left == nullptr) return root->right;else if(root->right == nullptr) return root->left;else{TreeNode* cur = root->right;        //找右子樹最左邊節點while(cur->left != nullptr)cur = cur->left;cur->left = root->left;TreeNode* tmp = root;root = root->right;delete tmp;return root;}}//如果沒有找到，繼續遍歷if(root->val > key) root->left = deleteNode(root->left,key);if(root->val < key) root->right = deleteNode(root->right,key);return root;}
};

669. 修剪二叉搜索樹
https://leetcode-cn.com/problems/trim-a-binary-search-tree/
如果當前結點的值小于low，要對該結點的右孩子進行再次搜索，直到找到滿足區間的結點或者空結點，最后返回right結點
如果當前結點的值大于high，要對該結點的左孩子進行再次搜索，直到找到滿足區間的結點或者空結點，最后返回left結點。
自上而下遍歷檢查，直到整棵樹遍歷完。
依次遍歷結點左右孩子，并將返回的結果作為當前結點的左右孩子。
最后返回當前結點。
返回的結點必然是val在區間內或者是空結點。

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == nullptr) return nullptr;if(root->val < low){//尋找新的節點TreeNode* right = trimBST(root->right,low,high);return right;}if(root->val > high){TreeNode* left = trimBST(root->left,low,high);return left;}//如果在這個區間內，那么就對左右子樹進行操作root->left = trimBST(root->left,low,high);root->right = trimBST(root->right,low,high);return root;}
};

108. 修剪二叉搜索樹
https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/\

class Solution {
public:TreeNode* traversal(vector<int>& nums,int left,int right){//這里我們定義區間是左閉右開的if(left == right) return nullptr;int mid = left + ((right-left) >> 1);TreeNode* node = new TreeNode(nums[mid]);node->left = traversal(nums,left,mid);node->right = traversal(nums,mid+1,right);return node;}TreeNode* sortedArrayToBST(vector<int>& nums) {if(nums.empty()) return nullptr;return traversal(nums,0,nums.size());}
};