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

假如用迭代的方式來解呢？

  1. 用 stack, 把要處理的放入，迴圈內每次都拿一個出來，做 最小可重複動作，做到 stack 沒東西為止
  2. 注意在放入 child 的時候這邊是用 reverse order 來放，因為我到時候拿出來的時候想用 .pop()(O(1) 時間複雜度) 而不是 .pop(0)(O(n) 時間複雜度)
Python 3 iterative solution
1
2
3
4
5
6
7
8
9
10
11
12
13
def preorder(self, root: 'Node') -> List[int]:
    if not root:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if not node.children:
            continue
        for child in reversed(node.children):
            stack.append(child)
    return res
# , , ,
733. Flood Fill
[Python] list 用 `.extend()` 與 `+=` 的差別

評論

分類

標籤雲

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

×