題目
思路
- Inorder Traversal: 對任意節點來說，順序為 左子樹 -> 自己 -> 右子樹
- 可拆解為最小單位動作，即第一點，故使用遞迴
Python 3 Recursive Solution1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
"""@return node values with inorder-traversal order"""
if not root:
return []
values = self.inorderTraversal(root.left)
values.append(root.val)
values.extend(self.inorderTraversal(root.right))
return values
|
這個題目使用遞迴是相對直觀的，以下改用 iterative 的方式來解：
思路：使用一個 list 當 stack 來放 nodes，只要按照順序放入，再從裡面依序把 node pop() 出來取 value，stack 為空的時候代表已處理完所有的 nodes => 回傳答案。以下列出主要分解動作：
把 root 和 root 所有的左節點由上到下依序放入 stack，放完後 stack 裡自然會包含左節點跟中間的節點
1
2
3
| while root:
stack.append(root)
root = root.left
|
把 node pop() 出來取 value，此時最先被 pop 出來的會是最下面的左節點。可以先參照後面的完整程式碼，當 node 為葉子節點時，不會有 node.right，所以下一個迴圈會繼續 pop 出中間的節點
1
2
| node = stack.pop()
values.append(node.val)
|
- 在
node = stack.pop() 之前先判斷 stack 是否還有，如為空代表所有的節點已被遍歷完，故回傳答案 values
左、中節點處理完後，處理右節點：把右節點當成新的 root，重複前兩步驟
root = node.right- 上面一行連同前兩步驟的程式碼，用
while True: 包起來
Python 3 Iterative Solution1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
"""@return node values with inorder-traversal order"""
if not root:
return []
stack, values = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return values
node = stack.pop()
values.append(node.val)
root = node.right
|
