將二元樹展平為Linked List| Medium | LeetCode#114. Flatten Binary Tree to Linked List
題目敘述 題目難度： Medium 題目敘述：給定一棵 Binary Tree 的 root，將 Binary tree 展平成一個 Linked List Linked List 要與題目的 TreeNode 是相同的 class，right child pointer 要指向list中的下一個節點，而 left child pointer 皆指向null Linked List 節點順序要與對這棵樹進行 Pre-order Traversal 的節點順序一樣 解法一開始的想法 這題的想法沒有花很久時間，算是解到目前最快的一題，大概從有想法到AC大概20min 這題的目的是要將一棵任意的二元樹轉換為一個往右側節點生長的Linked List (其實就是 skewed tree)。我一開始的想法如下： 首先宣告一個指標，用來指向 right subTree 的 root，走到任意節點時，如果他的左子樹存在，就將其左子樹嫁接到當前節點的右子樹位置，但這樣原先的右子樹怎辦？這就是剛剛要宣告一個新指標的原因。接著嫁接完畢後就將原本 right subTree 的 ro...
二元樹的右視圖 | Medium | LeetCode#199. Binary Tree Right Side View
題目敘述 題目難度: Medium 題目敘述: 這題要求給定一個 Binary Tree 的 root，請想像站在樹的右側，由上而下將節點列出。 解法一開始的想法我一開始直接理解錯題目，我以為題目要我們想像站在樹右側是正面面對樹，然後朝向右半側，所以覺得題目只是要我們列出除了ROOT之外右邊子樹的所有節點，但其實是要站在樹的右邊面向樹，由上往下看，因此有被遮擋住的節點就不會回傳。 所以如果是上面這棵樹，則會印出 [1,3,4] 我的解法12345678910111213141516171819202122232425262728293031323334353637/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNod...
所有 Root-Leaf 路徑總和 | Medium | LeetCode#129. Sum Root to Leaf Numbers
題目敘述 題目難度： Medium 題目描述：給定一個 Binary Tree 的 root，樹中的節點值為 0~9 的其中一個數字，從 Root 到 leaf 的節點值可以形成一個整數 ( 1->2->3 就代表 123 )，每一條從root到 leaf的路徑都有一個數字，本題需要你將每個數字加總。 題目有提示，回傳的整數會需要為 32-bit 整數 解法一開始的想法這次的想法就會是，這種題目就是可以用 dfs 或者是 bfs 來解，這次選用 dfs 並且在每次拜訪節點的時候去紀錄節點值，並且可以再回傳到原先的 caller 的時候將原先的路徑值乘上10 (才能夠形成一個 10 進位數字)，然後後夾到當前節點值，一路遞迴回去就能得到某一路徑的加總值。 之後再將所有路徑的和在加總起來回傳就好。 我的解法1234567891011121314151617181920212223242526272829303132333435/** * Definition for a binary tree node. * struct TreeNode { * ...
二元搜尋樹迭代器 | Medium | LeetCode#173. Binary Search Tree Iterator
題目敘述 題目難度： Easy 題目敘述： 題目要求你實作一個 BSTIterator 作為二元樹的 Iterator，可以對一個 Binary Search Tree 進行 in-order traversal BSTIterator(TreeNode root) 為 BSTIterator class 的 constructor，整個 BST 的 root 會作為 constructor 的初始參數 boolean hasNext() 會去檢查當前 pointer 的右側是否有值存在，如果有就回傳 true 否則則是 false int next() 則會將指標移動到下一個指標，並且回傳其指向的資料值 注意：第一次呼叫 next() 會需要回傳 null，可假設每次呼叫 next() 都會 valid，也就是每次呼叫都會至少有一個值可被回傳 （以 in-order traversal順序） 解法一開始的想法一開始有點被我的這篇文章誤導，我原先的想法也是要找到 leftmost 元素，接下來去找 successor (即下一個節點)，但下一個節點可能會是右子...
計算完整二元術節點 | Easy | LeetCode#222. Count Complete Tree Nodes
題目敘述 題目難度: Easy 題目敘述: 題目要求給定一個 Complete Binary Tree 的 root，需要計算 Tree 中的所有節點 根據維基百科定義，在一顆二元樹中，若除最後一層外的其餘層都是滿的，並且最後一層要麼是滿的，要麼在右邊缺少連續若干節點，則此二元樹為完全二元樹（Complete Binary Tree）。深度為k的完全二元樹，至少有 $\displaystyle 2^{\begin{aligned}k-1\end{aligned}}$ 個節點，至多有 $\displaystyle 2^{\begin{aligned}k\end{aligned}}-1$ 個節點。 最後題目有個要求是，請設計一套演算法其時間複雜度小於 $O(n)$ 解法一開始的想法這題我一開始的想法其實都是 $O(N)$ 的做法 (各種 Traversal 算節點)，到後面是想說，首先可以瘋狂往樹的左子樹走就可以知道整顆 Tree 的 leftmost 節點，這樣也就能夠知道這個Tree 的高度。 接下來只要能夠知道 leaf 數量就能夠得到節點總數了。 但為了找到 le...
二元樹路徑總和 | Easy | LeetCode#112. Path Sum
題目敘述 題目難度: Easy 題目敘述: 給定一個二元樹的 root 以及一個整數 targetSum，若從 root 到 任意leaf 之間節點值的加總等於 targetSum 則回傳 true 解法一開始的想法 這題一開始的想法就是用 DFS，去找到 root，途中運用變數來儲存節點值，邊traverse 邊累加節點值，走到leaf就能夠知道是否等於 targetSum 錯誤寫法1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : v...
透過 Preorder Traversal 和 Inorder Traversal 建構二元樹 | Medium | LeetCode#105. Construct Binary Tree from Preorder and Inorder Traversal
題目敘述 題目難度: Medium 題目敘述: 給兩個整數陣列 preorder 以及 inorder， preorder 存放一棵二元樹進行 Pre-Order Traversal 的結果，inorder 存放相同二元樹進行 In-Order Traversal 的結果，題目要求透過這兩個陣列來建構出原本的Binary Tree，並回傳 root 節點。 解法一開始的想法這次的題目卡了很久，主要流程有嘗試寫下想法，但不知道該如何用遞迴去實作。 字有點醜，請見諒XD 首先第一個想法就是，Preorder Traversal 後的第一個元素必定會是Root，而再來就是 Inorder Traversal 後的第一個元素會是整棵樹的 leftmost node，也就是最左邊的節點，所以如果能夠迭題目給的 preorder list，從 Root 到 leftmost node 之間的元素都會是左子樹的 left child。在 Preorder Traversal 中，root 節點的下一個節點會是左子樹的Root，這時檢查 inorder list 中， 左子樹的ro...
二元樹各層的平均值 | Easy | LeetCode#637. Average of Levels in Binary Tree
題目敘述 題目難度: Easy 題目敘述: 題目給定一個 Binary Tree 的 root，求各層level 節點值的平均值，結果以陣列回傳 解法一開始的想法這題與之前碰過的題目很像，**首先想法一樣會是先BFS (Level-Order Traversal)**。 如果能夠在各層加入某個變數，在各層結束時加入回傳陣列即可。 我的解法這是我一開始的解法，但這是錯的 123456789101112131415161718192021222324252627282930313233343536373839404142434445/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x),...
對稱的二元樹 | Easy | LeetCode#101. Symmetric Tree
題目敘述 題目難度: Easy 題目敘述: 給定一個二元樹的 root，題目要我們檢查該二元樹是否是對稱的。 解法一開始的想法我一開始的想法就錯了，我一開始認為只要 Inorder Traversal 後的結果，只要反向過來也一樣那就是對稱的了 所以我一開始的解法是錯的: 123456789101112131415161718192021vector<int> result_inorder;void BT::inorder(TreeNode* node){ if(node==NULL) return; cout << node->val << " "; result_inorder.push_back(node->val); inorder(node->left); inorder(node->right);};bool BT::isSymmetric(TreeNode* root){ bool result = fals...
二元樹 Level Order Traversal | Medium | LeetCode#102. Binary Tree Level Order Traversal
題目敘述 題目難度: Medium 題目敘述: 給定一個 Binary Tree 的 root，求 Level Order Traversal 的結果 (須將節點值存在一個二維list中) 解法一開始的想法就是先實踐經典的 Level Order Traversal，然後再嘗試存進 vector<vector<int>> result 返回。但我的想法在我剛實現完標準的 level_order_traversal 後就卡住了，由於我是用 queue 來去做實現，而每一次 push 進 queue後的節點會為同一層 (因為上一層已經被pop出來了) ，因此就可以處理在每一層的時候將節點值添加進 result 中，但我高估了我對 vector 的熟悉程度… 我的解法123456789101112131415161718192021222324252627282930313233343536373839404142434445/** * Definition for a binary tree node. * struct TreeNode { *...
