前言

簡單、中等 √ 好久沒更了，感覺二叉樹來回就那些。有點變懶要警醒，不能止步于笨方法！！

二叉樹的直徑

我的題解

遍歷每個節點，左節點最大深度+右節點最大深度+當前節點=當前節點為中心的直徑。如果左節點深度更大，向左遍歷，直到直徑不再更新。

class Solution {
public://最大深度int deepOfTree(TreeNode* root){if (!root)return 0;return max(deepOfTree(root->left), deepOfTree(root->right))+1;}int diameterOfBinaryTree(TreeNode* root) {TreeNode* node = root;int d = 0;int maxd = 0;while (node){int deepl = deepOfTree(node->left);int deepr = deepOfTree(node->right);d = deepl + deepr;maxd = max(maxd, d);if (deepl > deepr)node = node->left;else if (deepl < deepr)node = node->right;elsebreak;}return maxd;}
};

?上述方法耗時較長，原因是求最大深度和遍歷每個節點的直徑步驟重復了。優化后把直徑設為全局節點。保留遍歷最大深度函數，遍歷過程中順便更新直徑maxd = max(maxd, deepl+deepr);

class Solution {
public:int maxd = 0;//最大深度int deepOfTree(TreeNode* node){if (!node)return 0;int deepl = deepOfTree(node->left);int deepr = deepOfTree(node->right);maxd = max(maxd, deepl+deepr);return max(deepl, deepr)+1;}int diameterOfBinaryTree(TreeNode* root) {deepOfTree(root);return maxd;}
};

官解

與筆者的方法二一致

心得

最大深度的延申題。

二叉樹的層次遍歷

我的題解

廣度優先搜索，用一個隊列存節點和深度，根據深度保存答案。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if (!root) return {};vector<vector<int>> ans;queue<pair<TreeNode*, int>> q;q.push({root, 0});while (!q.empty()){TreeNode* node = q.front().first;int level = q.front().second;if (level >= ans.size())ans.push_back({node->val});elseans[level].push_back(node->val);if (node->left) q.push({node->left, level + 1});if (node->right) q.push({node->right, level + 1});q.pop();}return ans;}
};

官解

廣度優先搜索
思路和算法

我們可以用廣度優先搜索解決這個問題。

我們可以想到最樸素的方法是用一個二元組 (node, level) 來表示狀態，它表示某個節點和它所在的層數，每個新進隊列的節點的 level 值都是父親節點的 level 值加一。最后根據每個點的 level 對點進行分類，分類的時候我們可以利用哈希表，維護一個以 level 為鍵，對應節點值組成的數組為值，廣度優先搜索結束以后按鍵 level 從小到大取出所有值，組成答案返回即可。

考慮如何優化空間開銷：如何不用哈希映射，并且只用一個變量 node 表示狀態，實現這個功能呢？

我們可以用一種巧妙的方法修改廣度優先搜索：

首先根元素入隊
當隊列不為空的時候
求當前隊列的長度?
依次從隊列中取 元素進行拓展，然后進入下一次迭代
它和普通廣度優先搜索的區別在于，普通廣度優先搜索每次只取一個元素拓展，而這里每次取 元素。在上述過程中的第 i 次迭代就得到了二叉樹的元素。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector <vector <int>> ret;if (!root) {return ret;}queue <TreeNode*> q;q.push(root);while (!q.empty()) {int currentLevelSize = q.size();ret.push_back(vector <int> ());for (int i = 1; i <= currentLevelSize; ++i) {auto node = q.front(); q.pop();ret.back().push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return ret;}
};

心得

官解用了一個巧妙的方法節省了節點的深度信息。簡單來說就是同時把同一層的節點遍歷完。用currentLevelSize = q.size();記錄當前層有多少個節點，然后內嵌循環把這些節點都遍歷并且輸出。后續我也嘗試了這個方法但是漏了記錄當前層節點的關鍵步驟。之后會留意..

將有序數組轉換為二叉搜索樹

我的題解

有點像分治法，取中點作為當前節點建樹，左子樹取左邊數組作為新的數組建樹，右子樹取右邊。

class Solution {
public:TreeNode* sort(vector<int>& nums, int l, int r){if (l > r)return nullptr;int mid = (l + r)/2;TreeNode* root = new TreeNode(nums[mid]);root->left = sort(nums, l, mid-1);root->right = sort(nums, mid+1, r);return root; }TreeNode* sortedArrayToBST(vector<int>& nums) {if (nums.empty())return nullptr;TreeNode* root = new TreeNode();root = sort(nums, 0, nums.size()-1);return root;}
};

官解

官解與筆者思路一致，只是策略不同（左、右，隨機節點為子節點）

心得

有序數組轉換為二叉搜索樹還是比較簡單的，可以研究下無序數組如何轉換并且維護，應該跟最大堆差不多？

驗證二叉搜索樹

我的題解

左右子樹有三個點要驗證：1）子樹值與當前節點值比對；2）子樹是否也是二叉搜索樹；3）子樹的最大（右）/小（左）節點值與當前節點值比對。凡是一點不符合直接返回false，否則返回true。

class Solution {
public:bool isValidBST(TreeNode* root) {if (!root)return true;if (root->left){if (root->val <= root->left->val)return false;if (!isValidBST(root->left))return false;if (root->left->right){TreeNode* node = root->left->right;while (node->right){node = node->right;}if (root->val <= node->val)return false;}}if (root->right){if (root->val >= root->right->val)return false;if (!isValidBST(root->right))return false;if (root->right->left){TreeNode* node = root->right->left;while (node->left){node = node->left;}if (root->val >= node->val)return false;}}return true;}
};

官解

遞歸

要解決這道題首先我們要了解二叉搜索樹有什么性質可以給我們利用，由題目給出的信息我們可以知道：如果該二叉樹的左子樹不為空，則左子樹上所有節點的值均小于它的根節點的值； 若它的右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；它的左右子樹也為二叉搜索樹。

這啟示我們設計一個遞歸函數 helper(root, lower, upper) 來遞歸判斷，函數表示考慮以 root 為根的子樹，判斷子樹中所有節點的值是否都在 (l,r) 的范圍內（注意是開區間）。如果 root 節點的值 val 不在 (l,r) 的范圍內說明不滿足條件直接返回，否則我們要繼續遞歸調用檢查它的左右子樹是否滿足，如果都滿足才說明這是一棵二叉搜索樹。

那么根據二叉搜索樹的性質，在遞歸調用左子樹時，我們需要把上界 upper 改為 root.val，即調用 helper(root.left, lower, root.val)，因為左子樹里所有節點的值均小于它的根節點的值。同理遞歸調用右子樹時，我們需要把下界 lower 改為 root.val，即調用 helper(root.right, root.val, upper)。

函數遞歸調用的入口為 helper(root, -inf, +inf)， inf 表示一個無窮大的值。

class Solution {
public:bool helper(TreeNode* root, long long lower, long long upper) {if (root == nullptr) {return true;}if (root -> val <= lower || root -> val >= upper) {return false;}return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);}bool isValidBST(TreeNode* root) {return helper(root, LONG_MIN, LONG_MAX);}
};

中序遍歷

基于方法一中提及的性質，我們可以進一步知道二叉搜索樹「中序遍歷」得到的值構成的序列一定是升序的，這啟示我們在中序遍歷的時候實時檢查當前節點的值是否大于前一個中序遍歷到的節點的值即可。如果均大于說明這個序列是升序的，整棵樹是二叉搜索樹，否則不是，下面的代碼我們使用棧來模擬中序遍歷的過程。

可能有讀者不知道中序遍歷是什么，我們這里簡單提及。中序遍歷是二叉樹的一種遍歷方式，它先遍歷左子樹，再遍歷根節點，最后遍歷右子樹。而我們二叉搜索樹保證了左子樹的節點的值均小于根節點的值，根節點的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。

class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> stack;long long inorder = (long long)INT_MIN - 1;while (!stack.empty() || root != nullptr) {while (root != nullptr) {stack.push(root);root = root -> left;}root = stack.top();stack.pop();// 如果中序遍歷得到的節點的值小于等于前一個 inorder，說明不是二叉搜索樹if (root -> val <= inorder) {return false;}inorder = root -> val;root = root -> right;}return true;}
};

心得

兩個官解都是好方法。遞歸：輸入最大值和最小值，遍歷每個節點的值，在限定范圍內，左子樹的最大值更新為當前節點值，右子樹的最小值更新為當前節點值，子樹都為二叉搜索樹則返回true；迭代；迭代：中序遍歷，由于二叉搜索樹遍歷出來應該是升序排列，故如果當前節點小于等于前一節點，直接返回false。這個題考察對二叉搜索樹的理解，我的方法雖然繞過了long long但是太笨了！

二叉搜索樹中第K小的元素

我的題解

中序遍歷到第k個元素，return。

class Solution {
public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> forder;TreeNode* node = root;vector<int> ans;int count = 0;forder.push(node);while(!forder.empty()){while(node){forder.push(node);node = node->left;}node = forder.top();ans.push_back(node->val);forder.pop();node = node->right;count++;if (count == k)break;}return ans[k-1];}
};

官解

中序遍歷與筆者一致，不贅述。平衡二叉搜索樹的方法太長了，粗略看每個函數也不太難，性價比不高，以后再學習吧。

記錄子樹的結點數

我們之所以需要中序遍歷前 k 個元素，是因為我們不知道子樹的結點數量，不得不通過遍歷子樹的方式來獲知。

因此，我們可以記錄下以每個結點為根結點的子樹的結點數，并在查找第 k 小的值時，使用如下方法搜索：

令 node 等于根結點，開始搜索。

對當前結點 node 進行如下操作：

如果 node 的左子樹的結點數 left 小于 k?1，則第 k 小的元素一定在 node 的右子樹中，令 node 等于其的右子結點，k 等于 k?left?1，并繼續搜索；
如果 node 的左子樹的結點數 left 等于 k?1，則第 k 小的元素即為 node ，結束搜索并返回 node 即可；
如果 node 的左子樹的結點數 left 大于 k?1，則第 k 小的元素一定在 node 的左子樹中，令 node 等于其左子結點，并繼續搜索。
在實現中，我們既可以將以每個結點為根結點的子樹的結點數存儲在結點中，也可以將其記錄在哈希表中。

class MyBst {
public:MyBst(TreeNode *root) {this->root = root;countNodeNum(root);}// 返回二叉搜索樹中第k小的元素int kthSmallest(int k) {TreeNode *node = root;while (node != nullptr) {int left = getNodeNum(node->left);if (left < k - 1) {node = node->right;k -= left + 1;} else if (left == k - 1) {break;} else {node = node->left;}}return node->val;}private:TreeNode *root;unordered_map<TreeNode *, int> nodeNum;// 統計以node為根結點的子樹的結點數int countNodeNum(TreeNode * node) {if (node == nullptr) {return 0;}nodeNum[node] = 1 + countNodeNum(node->left) + countNodeNum(node->right);return nodeNum[node];}// 獲取以node為根結點的子樹的結點數int getNodeNum(TreeNode * node) {if (node != nullptr && nodeNum.count(node)) {return nodeNum[node];}else{return 0;}}
};class Solution {
public:int kthSmallest(TreeNode* root, int k) {MyBst bst(root);return bst.kthSmallest(k);}
};

心得

中序遍歷的迭代寫法還需要再鞏固，以當前節點為判斷條件，而不是以下一節點為判斷條件。記錄子樹的結點數的方法：首先要用一個哈希表記錄每個節點有多少顆子樹，計算過程定義count函數，獲取過程定義get函數。然后遍歷每個節點，如果子樹數量小于k，移到right，如果等于k，返回當前節點，大于k，移到left。感覺這個方法不是很能復用到其他題目上，但是count和get（哈希）這種分開的方式很值得我學習，是一種安全高效的獲取方式。

二叉樹的右視圖

我的題解

對二叉樹進行層次遍歷，把每一層的最后一個元素取出放入ans容器中。

class Solution {
public:vector<int> rightSideView(TreeNode* root) {if (!root)return {};queue<pair<TreeNode*, int>> q;vector<vector<int>> bfs;vector<int> ans;TreeNode* node = root;int level = 0;q.push({node, level});while (!q.empty()){node = q.front().first;level = q.front().second;q.pop();if (node->left) q.push({node->left, level+1});if (node->right) q.push({node->right, level+1});if (level >= bfs.size()) bfs.push_back({node->val});else bfs[level].push_back(node->val);}for (int i = 0; i < bfs.size(); i++){ans.push_back(bfs[i].back());}return ans;}
};

官解

廣度優先搜索/層次遍歷與筆者思路一致，不贅述。

深度優先搜索

我們對樹進行深度優先搜索，在搜索過程中，我們總是先訪問右子樹。那么對于每一層來說，我們在這層見到的第一個結點一定是最右邊的結點。

算法

這樣一來，我們可以存儲在每個深度訪問的第一個結點，一旦我們知道了樹的層數，就可以得到最終的結果數組。

上圖表示了問題的一個實例。紅色結點自上而下組成答案，邊緣以訪問順序標號。

class Solution {
public:vector<int> rightSideView(TreeNode* root) {unordered_map<int, int> rightmostValueAtDepth;int max_depth = -1;stack<TreeNode*> nodeStack;stack<int> depthStack;nodeStack.push(root);depthStack.push(0);while (!nodeStack.empty()) {TreeNode* node = nodeStack.top();nodeStack.pop();int depth = depthStack.top();depthStack.pop();if (node != NULL) {// 維護二叉樹的最大深度max_depth = max(max_depth, depth);// 如果不存在對應深度的節點我們才插入if (rightmostValueAtDepth.find(depth) == rightmostValueAtDepth.end()) {rightmostValueAtDepth[depth] =  node -> val;}nodeStack.push(node -> left);nodeStack.push(node -> right);depthStack.push(depth + 1);depthStack.push(depth + 1);}}vector<int> rightView;for (int depth = 0; depth <= max_depth; ++depth) {rightView.push_back(rightmostValueAtDepth[depth]);}return rightView;}
}; 

心得

層次遍歷的解法是直觀的解法。深度優先搜索的解法則是定義了哈希表記錄每個深度最右的節點。維護一個節點棧和深度棧，然后對二叉樹進行后序遍歷，如果當前深度沒有最右節點，則放入ans中。這個解法其實也與層次遍歷類似，只是顯式地用棧來維護深度信息。