iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 26
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 26

【從面試題學邏輯-26】在不使用遞迴的情況下後序走訪二元樹(leetcode 145. Binary Tree Postorder Traversal)

題目:
請實作一個後序走訪二元樹的方法

挑戰:
我們知道走訪二元數通常都是用遞迴,你可以在不使用遞迴的情況下搞定這題嗎?

點我前往LeetCode題目


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


本題接續昨日的題目,建議先看一下上一篇,相關的概念就不重複敘述了

可能大家會想說是不是依照昨天那樣,把val加到result,接著用stack來存之後往左走
但這樣會有個問題,我們舉一個比較極端的例子:

依照昨天的邏輯,我們先把1塞進去stack,接著碰到左邊沒有Node,所以1又拿出來。但這時我們沒有要拿1的值,要走右邊之後把1塞回去stack嗎?不行,這樣沒辦法辨識誰是要走右邊,誰是要拿val

因此我們要改點作法,但這次的做法比較不好理解,我們直接從程式碼解釋:

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<Integer>();
        if(root==null) return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode currentNode = root;
        stack.push(currentNode);
        while(!stack.isEmpty())
        {
            currentNode = stack.pop();
            result.addFirst(currentNode.val);
            if(currentNode.left!=null) stack.push(currentNode.left);
            if(currentNode.right!=null) stack.push(currentNode.right);
        }
        return result;
    }
}
LinkedList<Integer> result = new LinkedList<Integer>();
if(root==null) return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode currentNode = root;
stack.push(currentNode);

這些基本的東西就不多解釋了

while(!stack.isEmpty())
{
    currentNode = stack.pop();
    result.addFirst(currentNode.val);
    if(currentNode.left!=null) stack.push(currentNode.left);
    if(currentNode.right!=null) stack.push(currentNode.right);
}

那重點的這一段是什麼意思?

首先,後序的讀取順序應該要像下圖這樣

先左邊,再右邊,最後才是自己

而上面的解法是倒過來加答案,上面用了一個addFirst()的方法,它可以幫我們把數字加到最前面。如果每次我們加東西都加在最前面,第一個加進來的東西就會是result內的最後一個對吧?

好像很難懂,我們舉個例子看看

         A
       /   \
     B       E
    / \     / \
   C   D   F   G

照上面程式碼的步驟走一次吧

  1. 首先把root的A塞進stack中
  2. 進入while迴圈
  3. stack pop,currentNode是A
  4. 把A加到result最前方,現在result中有[A]
  5. 把B塞進stack,再把E塞進stack,stack中現在有[E,B]
  6. stack pop,currentNode現在是E
  7. 把E加到result最前方,現在result中有[E,A]
  8. 把F塞進stack,再把G塞進stack,stack中現在有[G,F,B]
  9. stack pop,currentNode現在是G
  10. G下面沒有Node,所以G直接進result最前方,result中現在有[G,E,A]
  11. stack pop,currentNode現在是F
  12. F下面沒有Node,所以F直接進result最前方,result中現在有[F,G,E,A]
  13. stack pop,currentNode現在是B(注意這裡切換到root左邊了)
  14. 把B加到result最前方,現在result中有[B,F,G,E,A]
  15. 把C塞進stack,再把D塞進stack,stack中現在有[D,C]
  16. stack pop,currentNode現在是D
  17. D下面沒有Node,所以D直接進result最前方,result中現在有[D,B,F,G,E,A]
  18. stack pop,currentNode現在是C
  19. C下面沒有Node,所以C直接進result最前方,result中現在有[C,D,B,F,G,E,A]
  20. stack空了,輸出答案

我們拿到的root,本身就是後序走訪中的最後一個,我們剛好可以利用這一點,反過來加答案。

每一次我們到的新Node,把它之下的整個結構,想像成是一棵小一點的二元樹,這樣那顆新的Node就變成另一個root了對吧?
那新的Node就都是最後一個讀取的,所以就把它加到最前面,再往下找其他Node。while迴圈內就是在處理這一件事


上一篇
【從面試題學邏輯-25】在不使用遞迴的情況下先序走訪二元樹(leetcode 144. Binary Tree Preorder Traversal)
下一篇
【從面試題學邏輯-27】首次體驗到有效率沒效率的題目(leetcode 11. Container With Most Water)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言