Leetcode — 94. Binary Tree Inorder Traversal (中文)

問題連結: https://leetcode.com/problems/binary-tree-inorder-traversal/

題目給一個binary tree名為root,回傳用inorder traversal這棵樹所有值的list

範例 root = [1,2,3,4,5,null,7] (下方有示意圖)
則inorder list 應為 [4,2,5,1,3,7]

root = [1,2,3,4,5,null,7]

想法:

如果你知道inorder 的概念的話, 這題如果要做遞迴應該不會太困難

Inorder 是其中一種tree traversal的方式, 我們每次都是先跑node的左子點, 才跑node本身值,最後再跑其右子點
也因為這樣的跑法, 如果我們inorder來跑一個binary search tree, 我們可以得一個排序的陣列 (因為bst的特性就是左子樹永遠小於右子樹)

而直接按照我們inorder的邏輯, 我們也可以得到以下的程式碼 -

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        helper(list,root);
        return list;
    }
    public void helper(List<Integer> list, TreeNode node){
        if(node==null)
            return;
        helper(list,node.left);
        list.add(node.val);
        helper(list,node.right);
    }

但如果在面試中只寫得出這樣遞迴的答案, 想必面試考官也不會滿意
他們會問你follow up questions 希望你可以用iterative的方式得到一樣效果

因為我們不能利用helper method來幫我們traverse整個樹, 我們需要一個什麼東西來幫我們存我們之後會用到的node
現在我可以想到兩種結構, 我們該用 queue還是stack ?😕

如果我們選擇用queue (先進先出) 那我們每次都會拿我們最一開始放的node 所以變成我們會先拿node本身 才拿他的左子點或右子點 (畢竟我們一開始得到的node就是root, 我們放的第一個node一定是root, 感覺如果我們是需要traverse tree by level, 用queue就會比較適合!)

但如果我們用stack(後進先出) 我們就可以一直放node 還有他的子點們, 這樣等等我們第一個先拿到的node就會是我們最後才放的了 (例如如果我們一直放node跟他的左子點們, 我們第一個拿到的就會是原本node的leftmost node)

💭 也就是說 對付這種inorder 類型題目, 用stack來輔助我們會比較適合! 😄

程式邏輯

我們將有3個變數來輔佐我們—

1. node: 紀錄我們現在想要traverse的子點。我們想要traverse這個node以及他的所有的左子點們，並且把他們都放進stack裡
2. stack: 放著我們等待著放進list的子點們, 而當我們放進list後, 我們下一個traverse的node就會是這個剛放進inorder list的右子點及這個右子點的左子點們
3. list: 也就是存著我們最終結果的inorder list

在程式裡我們會一直用loop來traverse在樹裡的所有點, 直到node 是null 且stack裡面也沒有等待我們來traverse的nodes了.

✏️在stack中, 我們存的其實是TreeNode型態, 而非單一value值, 但下面的步驟圖們為了讓圖不要太擠.我只列出TreeNode的root們來做表示

可以想成我們永遠都是最先traverse 一個node的所有左子點 並把它們放進stack中 而node進入inorder list的順序就是看它何時從stack被取出來 我們永遠都是先把node放進stack中, 讓node在stack中等著被取出來, node不時還會被他的左晚輩們插隊

那你就會想說, 咦 那我們何時考慮到右子點呢 😟 我們在每次把node放進inorder list後 下一步就是換traverse這個node的右子樹了

🔧Step 1. 最初狀態, list 和 stack 最初為空, node則是我們最初的root

initial state

🔧Step 2. 把curret node跟其所有的左子點們都放進stack中, 為了traverse node 的所有左子點們, node現在為null

step 2 result

🔧Step 3. 這時, 我們選擇stack中最左的node (也就是放在最頂端的node), 把它取出來, 並把值放進inorder list中。把node放進inorder list的下一步就是換traverse 這個node的右子樹, 因此讓node = “剛剛拿出的node”.right (i.e., stack.pop().right)

step 3 result

🔧Step 4. 把所有current node及其左子點都放進 stack — 因為node目前是null 所以沒有增加任何node到stack裡
我們把目前最近期放入stack中的子點拿出來(i.e., 2) 放進inorder list, 而把node放進inorder list的下一步就是換traverse 這個node的右子樹, 因此讓node = “剛剛拿出的node”.right (也就是5)

step 4 result

🔧Step 5. 把所有current node及其左子點都放進 stack — 因為5沒有任何左子點,所以只有把5放進去stack。
我們再把目前最近期放入stack中的子點拿出來(i.e., 5) 放進inorder list, 而把node放進inorder list的下一步就是換traverse 這個node的右子樹, 因此讓node = “剛剛拿出的node”.right (也就是null)

step 5 result

🔧Step 6. 把所有current node及其左子點都放進 stack — 因為node目前是null 所以沒有增加任何node到stack裡
我們再把目前最近期放入stack中的子點拿出來(i.e., 1) 放進inorder list, 而把node放進inorder list的下一步就是換traverse 這個node的右子樹, 因此讓node = “剛剛拿出的node”.right (也就是3)

step 6 result

🔧Step 7. 把所有current node及其左子點都放進 stack — 因為3沒有任何左子點,所以只有把3放進去stack。
我們再把目前最近期放入stack中的子點拿出來(i.e., 3) 放進inorder list, 而把node放進inorder list的下一步就是換traverse 這個node的右子樹, 因此讓node = “剛剛拿出的node”.right (也就是7)

step 7 result

🔧Step 8. 把所有current node及其左子點都放進 stack — 因為7沒有任何左子點,所以只有把7放進去stack。
我們再把目前最近期放入stack中的子點拿出來(i.e., 7) 放進inorder list, 而把node放進inorder list的下一步就是換traverse 這個node的右子樹, 因此讓node = “剛剛拿出的node”.right (也就是null)

step 8 result

🔧Step 9. 現在node為空值且stack也沒有其他的nodes等我們加了list中, 所以我們已完成inorder traversal

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while(node!=null || !stack.isEmpty())
        {
            while(node!=null)
            {
                stack.push(node);
                node = node.left;
            }
            list.add(stack.peek().val); //take the top node value
            node = stack.pop().right; //node be the right node
        }
        return list;
    }

Both the recursive solution and iterative solution are 0ms code that beat 100%.