Kevin Liu's 部落格 || Technical || Travel

題目敘述 題目難度：Medium 題目敘述：給定一個 Binary Search Tree 的 root，以及一個整數 k ，回傳第 $k^{th}$ 小的節點值 解法 這題是刷題到目前下來解最快的一題，從打開題目到最後 Accept 大概花 15 分鐘，其中包含 5 分鐘在local端手動寫測試 一開始的想法題目要求回傳 第 K 個最小的節點值，所以想法很簡單，首先 BST 的由左至右的大小排序跟你對樹進行 In-Order Traversal 的順序會一致，因此當你進行 In-Order Traversal 第一個拜訪的節點就會是最小值，接著拜訪到的就是 BST 中第二小的節點，依序下去…。 因此只要透過一個 counter 來計算現在是否第K個節點就好，如果找到就回傳節點值。 我的解法12345678910111213141516171819202122232425262728 ...

題目敘述 題目難度：Medium 題目敘述：給定一個二元樹的 root ，回傳對這棵樹進行 Z 字走訪 (Zigzag Level Order Traversal)的結果 Zigzag Level Order Traversal 代表先從左走到右，下一層再從右走到左，每一層走訪方向交互替換 解法一開始的想法這題想法也很直觀，就BFS，然後宣告一個用來存放結果的 2D Vector，透過變數控制在每一層走訪的時候，按照順序或反向順序放入 vector 當中。 我的解法123456789101112131415161718192021222324252627282930313233343536373839/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeN ...

題目敘述 題目難度： Medium 題目敘述： 題目給定一個 Binary Tree 的 root ，我們需要確認這棵 Binary Tree 是否是 Binary Search Tree 一個 valid 的 Binary Search Tree(BST) 包含了： 對於任意節點，其 Left SubTree 的任意節點值一定小於當前節點值 對於任意節點，其節點值一定小於其 Right SubTree 的任意節點值 Left SubTree 和 Right SubTree 都要是 binary search tree 解法一開始的想法這題想法很簡單，這題的花費時間很少，首先可以知道的是： BST 從小到大走訪，其走訪順序會是對同一棵樹進行 inorder traversal。 所以只要能夠 在 Inorder 走訪過程中比較前一個節點值與當前節點值，看前一個節點是否比當前節 ...

函式指標 (Function Pointer) 當你透過 C/C++ 中宣告一個函式時，就會分配一段起始記憶體位址，而 Function Pointer 就可以用來指向以及儲存函式位址。 所以我們可以直接透過 Function Pointer 1.來呼叫一個函式 2.或者將它傳遞給其他函式 用法宣告： 1[回傳值的data type] (* function pointer name)(input parameter1, input parameter2, ...); 記得需要將函數的位址 assign 給 function pointer，可以透過取位址運算子 & 來進行，這裡看下方範例： 1234567891011121314#include <iostream>using namespace std;int add(int a, int b)&# ...

題目敘述 題目難度： Easy 題目敘述： 給定一個 Binary Search Tree (BST) 的 root ，回傳樹中任意兩個節點的絕對值當中最小的。 解法一開始的想法首先 Binary Search Tree 的特性就是對於任意節點， 其左子樹必定 < 當前節點 < 右子樹。 因此可以判斷，在對這顆樹進行 Inorder Traversal 的過程中，相鄰節點的差值會是最小的，不存在跨一個節點之間差值更小的問題 所以基本上我的想法就是跑一遍 Inorder Traversal，將節點記錄到一個 list，在 list 中再計算差值．但這樣缺點就是 runtime 會增加。 我的解法123456789101112131415161718192021222324252627282930313233343536/** * Definition for a binar ...

題目敘述 題目難度： 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， ...

題目敘述 題目難度: Medium 題目敘述: 這題要求給定一個 Binary Tree 的 root，請想像站在樹的右側，由上而下將節點列出。 解法一開始的想法我一開始直接理解錯題目，我以為題目要我們想像站在樹右側是正面面對樹，然後朝向右半側，所以覺得題目只是要我們列出除了ROOT之外右邊子樹的所有節點，但其實是要站在樹的右邊面向樹，由上往下看，因此有被遮擋住的節點就不會回傳。 所以如果是上面這棵樹，則會印出 [1,3,4] 我的解法12345678910111213141516171819202122232425262728293031323334353637/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * Tre ...

題目敘述 題目難度： Medium 題目描述：給定一個 Binary Tree 的 root，樹中的節點值為 0~9 的其中一個數字，從 Root 到 leaf 的節點值可以形成一個整數 ( 1->2->3 就代表 123 )，每一條從root到 leaf的路徑都有一個數字，本題需要你將每個數字加總。 題目有提示，回傳的整數會需要為 32-bit 整數 解法一開始的想法這次的想法就會是，這種題目就是可以用 dfs 或者是 bfs 來解，這次選用 dfs 並且在每次拜訪節點的時候去紀錄節點值，並且可以再回傳到原先的 caller 的時候將原先的路徑值乘上10 (才能夠形成一個 10 進位數字)，然後後夾到當前節點值，一路遞迴回去就能得到某一路徑的加總值。 之後再將所有路徑的和在加總起來回傳就好。 我的解法123456789101112131415161718192021 ...

題目敘述 題目難度： 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 tra ...

題目敘述 題目難度: 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 算節點)，到後面是想說， ...