LeetCode Digest
2 分鐘 閱讀文 (大約 285 個字)

589. N-ary Tree Preorder Traversal

題目
思路

  1. 樹的問題會先從遞迴來想比較直觀，首先找出最小可重複動作來作為 recursive case
  2. 先假設我們可以用題目給的 method 直接當作遞迴的函式，也就是說我們遞迴函式的回傳，是 preorder 排序的 node values
  3. 最小可重複動作：對於我這個 node 來說，回傳 preordered values
Python 3 solution
1
2
3
4
5
6
7
def preorder(self, root: 'Node') -> List[int]:
    if not root:
        return []
    result = [root.val]
    for child in root.children or []:
        result.extend(self.preorder(child))
    return result
繼續閱讀
LeetCode Digest
4 分鐘 閱讀文 (大約 535 個字)

Validate Binary Search Tree

題目
思路

  1. 樹的問題用遞迴來解相對上比較直覺，所以先試試遞迴解
  2. 拆解到最小單位來找 recursive case: 隨機取樹中一個點，判斷它是否 valid
  3. 大部分情況都會有上下限。以左邊的點為例，上限就是父節點的值，下限就是它所在的右子樹的父節點的值，所以這個值必須由上到下一層層傳遞下來。反之，右邊的點的話，就變成上限必須一層層傳遞下來
  4. 因為上下限必須用傳遞的，所以寫一個 function node_valid 接受上下限的參數
繼續閱讀
LeetCode Digest
2 分鐘 閱讀文 (大約 293 個字)

Binary Tree Level Order Traversal

題目
思路

  1. 一次一層很直覺想到廣先搜尋 (BFS)，所以用 iterative 的做法來解
  2. 一次迴圈處理一層，並把下一層節點放入 stack 繼續在下次迴圈處理
    • stack 也是 list of list, 裡面的每個 list 都是一層節點
繼續閱讀
LeetCode Digest
4 分鐘 閱讀文 (大約 547 個字)

Binary Tree Inorder Traversal

題目
思路

  1. Inorder Traversal: 對任意節點來說，順序為 左子樹 -> 自己 -> 右子樹
  2. 可拆解為最小單位動作，即第一點，故使用遞迴
繼續閱讀
LeetCode Digest
3 分鐘 閱讀文 (大約 504 個字)

Merge Two Binary Trees

題目

做法一：recursive - DFS

  1. 找出最小的可重複動作：merge 兩個 nodes

    • 題目給的 method 就可以用來做遞迴

  2. 假設 mergeTrees 已完成，實作此最小可重複動作 

    1
    2
    3
    4
    root1.val += root2.val
    root1.left = self.mergeTrees(root1.left, root2.left)
    root1.right = self.mergeTrees(root1.right, root2.right)
    return root1
繼續閱讀
LeetCode Digest
4 分鐘 閱讀文 (大約 625 個字)

Balanced Binary Tree

題目

做法一

思路：

  1. 依照 height-balanced 的定義，需要符合每個node 的左右子樹高度差都不大於 1
  2. 假設有個 function height 可以回傳 node 的 height
    • 先不實作內容
  3. 使用這個 height 完成 isBalanced
繼續閱讀
LeetCode Digest
2 分鐘 閱讀文 (大約 329 個字)

Same Tree

題目
思路：

  1. 先用以樹來說較直觀的遞迴解
  1. 要比較所有相同位置的 node 的值是否一樣，可以把所有待比較的 node pair 丟到 stack 裡一一拿出來比較，全部比完都通過的話就是一樣的 tree
  2. 一個 pair 比較後會把下面的所有分支點繼續丟進 stack 等待比較，所以用 while stack: 只要有就繼續比，一直比到完
    • 此為廣先搜尋 (Breadth-First Search)
繼續閱讀

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×