刷題日記(5)Binary Tree Inorder Traversal

Rachel Yeh
6 min readDec 27, 2020

94. Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

首先,回朔一下Pre Order, In Order, Post Order的定義

三種order

— — — — — —-<解法1> — — — — — — —

解題思路:

1. 首先訪問左子樹,將左子樹存入stack中

2. 每次將stack最上面那個node值存入結果的Array List

3. 如果右子樹為空,取出stack最上方的node

4. 如果當前node1 為stack最上方node的right就一直pop stack的node, 直到目前的node不等於stack 最上方的node的right (這裡表示了訪問右子樹,根節點root已經被訪問過,彈出即可)

5. 如果當前node右子樹不為空,訪問右子樹,然後繼續遍歷左子樹,存入stack中

以這個為例子

(main function)

— — — — -— (第一大步驟) — — — — — — -

1. 首先新增一個空的stack, 以及一個空的Array List

2. 當root不等於null時 (就是一直往左走直到null)

2.1 stack 把root node push 進去

2.2 root等於root的left

2.3 直到root等於null結束迴圈

3. 此時stack有上面放入stack的左子樹的左孩子跟左孫子們以及root

— — — — - — (第二大步驟) — — — — — — -

4. 當stack不為空時

4.1 偷看一下stack最上面的node然後拿一個node label接住他

4.2 把這個node的val放入 前面新增放置結果的Array List中

— — — — — — (第三大步驟) — — — — — — -

(由於範例關係,會先跑程式碼中的else部分)

(第三和第四大步驟都是處理右邊為空和不為空,處理完就回到while迴圈的一開始的 peek 和add value)

4.3 如果(if)這個node的右邊不為空,就把這個node的right assign給node

4.3.1 當node不等於null時

4.3.1.1 把node(父親) push進stack裡,然後把node的 left assign給node(一路往下加入左孩子.左孫子….)迴圈…直到node標籤到 null 身上, (這時stack的top會是最左邊最下方的那個 node)

接著因為if/else結束第一次(當右邊不為空),所以又回到了4.1 & 4.2

4.1 偷看一下stack最上面的node然後拿一個node label接住他

4.2 把這個node的val放入 前面新增放置結果的Array List中

— — — — — — (第四大步驟) — — — — — — -

4.4 如果(if) 這個node的右邊為空, 就把stack中最上方的node pop出去(剛剛最後一個加入的最左下方的左孩子), 然後assign pop出去的node給原本的node(所以現在的node 是剛剛pop出來的)

接著剛剛的node不等於stack下一個top(也就是2的right), 所以這次的(if/else)跑完再度回到了最外面的迴圈

4.1 偷看一下stack最上面的node然後拿一個node label接住他

4.2 把這個node的val放入 前面新增放置結果的Array List中

然後因為node的右邊為空,所以再度重複4.4

4.4 如果(if) 這個node的右邊為空, 就把stack中最上方的node pop出去, 然後assign pop出去的node給原本的node(所以現在的node 是剛剛pop出來的)

4.4.1 當stack不為空 以及 stack再度偷看一下最上面的node的right是等於剛剛pop出來的那個node時

4.4.1.1 pop剛剛偷看的stack的那個node, 然後覆蓋原本的node

5. Stack為空時 回傳結果的Array List

— — — — — — — — — — — (結束) — — — — — — — — — —

— — — — — — -<解法1 End> — — — — — — —

Sign up to discover human stories that deepen your understanding of the world.

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet

Write a response