116. Populating Next Right Pointers in Each Node
題目網址：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
題意：給一 perfect BT, 其所有 leaf 皆在同一層, 且每個 non-leaf 皆有兩個 child。BT 定義如下:
填充每個 node 的 next, 讓 next 指向其右邊的 node。若右邊沒有 node, 則指向 NULL。所有 next 預設皆為 NULL。
進階：
設計 $O(1)$ space 的演算法
可以使用遞迴解題, 遞迴所用到的 stack space 不算做額外的 space
Solution 1：
想法：利用 BFS
class Solution {public: Node* connect(Node* root) { if (!root) { return root; } queue<Node*> q; q.emplace(root); ...
117. Populating Next Right Pointers in Each Node II
題目網址：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/
題意：給一 BT, 其中每一個 node 的定義如下:
將每個 node 的 next 指向其右邊的 node。若不存在右邊的 node, 則 next 應指向 NULL。所有 next 預設皆為 NULL。
進階：
設計 $O(1)$ space 的演算法
可以使用遞迴解題, 遞迴所用到的 stack space 不算做額外的 space
Solution 1：
想法：利用 BFS
class Solution {public: Node* connect(Node* root) { if (!root) { return root; } queue<Node*> q; q.emplace(root); while (!q.empty()) { ...
863. All Nodes Distance K in Binary Tree
題目網址：https://leetcode.cn/problems/all-nodes-distance-k-in-binary-tree/
題意：給一 BT 的 root, 和一目標點 target, 以及一整數 k。
返回所有距離目標點 target 為 k 的 node, 可以用任何順序返回。
tree 中每個 node.val 都不同。
Solution：
想法：利用 DFS + BFS
先用 DFS 建立無向圖
再以 target 為中心向外做 BFS
e.g. target = 5, k = 2
以 5 為中心, 首先取出 3, 6, 2
然後 3 會取出 5, 1
依此類推…
這邊必須小心, 因為我們建立的是無向圖, child 的 adj list 中是會有 parent 的以上面的為例, 3 向外擴散取出 5 跟 1。其中 1 是答案, 但 5 不是因此, 得用一個 visited 來記錄拜訪過的 node
若已經在 visited 裡則跳過
否則, 將其加入 visited 中
這樣一來, 5 最一開始就會被加入到 visited 中就算後面的 ...
113. Path Sum II
題目網址：https://leetcode.cn/problems/path-sum-ii/
題意：給一 BT 的 root 和一整數 targetSum, 返回所有 root-to-leaf 之路徑總和為 targetSum 的 path。
Solution 1：
想法：利用 DFS + Backtracking
class Solution {public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) { dfs(root, targetSum); return res; }private: vector<int> cur; vector<vector<int>> res; void dfs(TreeNode* root, int targetSum){ if (!root) { return; ...
236. Lowest Common Ancestor of a Binary Tree
題目網址：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
題意：給一 BT 和兩 node p 和 q, 找出他們的 lowest common ancestor（LCA）T。
Solution：
想法：利用 DFS, 主要分成以三種情形：
無法在左子樹找到任何 target node, 代表 LCA 不可能在左子樹中, 因此 return 右子樹的結果。
無法在右子樹找到任何 target node, 代表 LCA 不可能在右子樹中, 因此 return 左子樹的結果。
若可分別在左右子樹中找到 target node, 代表 current root 為所求
e.g. 下圖中, root = 1, p = 4, q = 10
以 2 為 root 時進行遞迴:
left：return 4
right：return 10
以 1 為 root 時進行遞迴:
left：return 2 (因為其 left, right 皆非 null)
right：return null
...