DAY 18
1
Software Development

## [Day 18] 從LeetCode學演算法 - 0094. Binary Tree Inorder Traversal (Medium)

``````Question:
Given a binary tree, return the inorder traversal of its nodes’ values.
``````
``````Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
``````
``````Follow up: Recursive solution is trivial, could you do it iteratively?
``````

``````inorder(root) {
if root == NIL return
inorder(root.left)
print(root.val) // Or add/append to the list
inorder(root.right)
}
``````

Java:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) return;
inorder(root.left, res);
inorder(root.right, res);
}
}
``````

Python:

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.inorder(root, res)
return res

def inorder(self, root: TreeNode, res: List[int]) -> None:
if not root: return
self.inorder(root.left, res)
res.append(root.val)
self.inorder(root.right, res)
``````

(這個堆疊又叫做The Stack或Call stack(呼叫堆疊))

1. 在In-order的流程中，首先我們是先一路走到最左邊的node，
中途經過的node我們應該要將其放進Stack中，這樣才能回到上一層去，
我們將這個node暫時命名為curr(current)。
2. curr一路向左最終一定會遇到NIL，表示這排從root一路向左邊走，
沿途的node全數放入到Stack中了
3. 那麼我們應該要將最後一個node從Stack中拿出來
(因為後進先出，最後一個node應該是最左邊的node才對)，將其放到list當中。
4. 接著將curr設為自己右邊的node。
5. 反覆上面的流程，一直到curr和stack都空掉為止。

``````create a list named res
create a stack named stack
curr = root
while ( curr != NIL or !stack.isEmpty() ) {
while (curr != NIL) {
stack.push(curr)
curr = curr.left
}
curr = stack.pop()
curr = curr.right
}
return res
``````

Java:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right;
}
return res;
}
}
``````

Python:

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
res.append(curr.val)
curr = curr.right
return res
``````

「時間/空間複雜度？」
（O(N), O(N)，因為要走訪過整棵樹，且list要儲存整個二元樹攤平的結果）

「如果我將res放在class Solution的level有什麼優缺點？」
(優點：

0124. Binary Tree Maximum Path Sum (Hard)