199. Binary Tree Right Side View
題目網址：https://leetcode.cn/problems/binary-tree-right-side-view/
題意：給一 BT 的 root, 想像你站在 BT 的右側, 按照從頂部到底部的順序, 返回你從右側所能看到的 node.val。
Solution 1：
想法：利用 BFS
class Solution {public: vector<int> rightSideView(TreeNode* root) { if (!root) { return {}; } vector<int> res; queue<TreeNode*> q; q.emplace(root); while (!q.empty()) { for (int i = q.size(); i > 0; --i) { ...
1448. Count Good Nodes in Binary Tree
題目網址：https://leetcode.cn/problems/count-good-nodes-in-binary-tree/
題意：給一 BT 的 root, 返回 BT 中 Good node 的個數。
Good node x 的定義：從 root 到 x 所經過的 node 中, 沒有任何 node.val 大於 x.val。
Solution：
想法：利用 DFS, 在 DFS 過程中維護當前路徑的最大值 curMax。若 node->val ≥ curMax, 則更新 maxCur, 並返回 1 + 左子樹的 good node 數 + 右子樹的 good node 數, 那個 1 是把當前 node 視為 good node
class Solution {public: int goodNodes(TreeNode* root) { return dfs(root, root->val); }private: // dfs(root, curMax) 返回 root 到 node 的 ...
98. Validate Binary Search Tree
題目網址：https://leetcode.cn/problems/validate-binary-search-tree/
題意：給一 BT 的 root, 返回其是否為 BST。
Solution：
想法：利用 DFS, 當前 node 必須判斷是否在目前的上、下界中, 因此要不斷維護當前的上、下界。若 node->val 滿足當前上下界：
遞迴遍歷 node->left, 並把 node->val 設為上界
遞迴遍歷 node->right, 並把 node->val 設為下界
下圖中雖然 7 > 4, 但它卻位於 5 的左子樹中（此時的 lower = 4, upper = 5）, 故要返回 false
class Solution {public: bool isValidBST(TreeNode* root) { // 要用 long 而非 int, 因為若用 int, 當 root = [INT_MAX] 時, 會返回 false return dfs(root, ...
230. Kth Smallest Element in a BST
題目網址：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
題意：給一 BST 的 root 和一整數 k, 返回 BST 中第 k 小的元素（從 1 開始計數）。
Solution：
想法：利用 BFS（inorder）, 不斷取當前 node 的 left 直到 node->left 為 null, 由於 left child 是「後進先出」, 故要使用 stack。將這些 left 一個一個 pop 掉, 並將 k 減去 1
若 k == 0, 代表當前 node 為第 k 小的數
若 k > 0, 代表當前的數還太小, 故要嘗試其右子樹中的 node
class Solution {public: int kthSmallest(TreeNode* root, int k) { stack<TreeNode*> stk; stk.emplace(root); while (!stk.empty()) &# ...
105. Construct Binary Tree from Preorder and Inorder Traversal
題目網址：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
題意：給一 BT 的 preorder 和 inorder, 構建並返回該 BT。
tree 中沒有重複的元素。
Solution：
想法：利用 DFS, 跟 654. Maximum Binary Tree 類似, 只是可以先遍歷 inorder, 紀錄 inorder 元素的 idx, 讓後續遍歷 preorder 元素時可快速定位, 將時間複雜度降到 $O(n)$
class Solution {public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { cur = 0; // 紀錄 inorder 元素的 idx, 方便 preorder 快速定位 for (int i = 0; i < ...