iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 25
0
自我挑戰組

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

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

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

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

點我前往LeetCode題目


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

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


好,相信知道二元樹的情況下,用遞迴走完都不是問題,但題目希望我們挑戰不用遞迴來走完

我們先列出一些重點再來想想要如何解:

  1. Node有先後順序問題,先序就是「印出當下Node的val→走左邊→走右邊」,也就是下面還有Node的話,要把當下的Node先記起來,左邊走完再回來這個Node找右邊的Node
  2. 下一個Node如果又有Node往下,就又必須記Node
  3. 最後記的Node要優先走,然後依序往回找Node

這樣聽起來……似乎stack會符合我們的需求,我們就利用stack後進先出的概念來記Node

我們實際利用程式碼來講解吧!

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

我們用一個currentNode來幫我們指引明燈指出目前我們正在哪個Node
stack則是幫我們暫時記住上面提到的,下面還有Node的Node
result顧名思義就是放結果

while(!stack.isEmpty() || currentNode!=null)

如果stack中還有Node,代表我們是從某個Node往下走,所以還要往回走。而如果stack沒了,currentNode也是空的,就代表我們走完整個二元樹了

if(currentNode!=null){
    result.add(currentNode.val);
    stack.push(currentNode);
    currentNode = currentNode.left;
} else {
    currentNode = stack.pop();
    currentNode = currentNode.right;
}

好的,currentNode!=null是要幹嘛呢?如果他是null的話,代表說stack內有東西的情況下,讀不到東西,代表說我們應該要回頭找右邊的Node了

我們上一個Node存在stack中,所以我們把currentNode移動到stack出來的Node。因為我們是先序走訪,所以這個Node的val已經加過了,就索性直接往右邊走吧

而如果currentNode不是null呢?就更簡單啦,我們把這個currentNode的val丟進result中,然後把currentNode丟到stack中,直接看看他的左邊有沒有Node(沒有的話,下次就會直接走到else中,把這個Node pop掉啦)


那其實LeetCode上先中後序都有出現,中序的概念和這題差不多,大家可以試試看用這一題的邏輯寫出答案(就幾行換個位子而已,免驚)

那後序呢?是不是差不多?/images/emoticon/emoticon14.gif

才怪!不一樣啦!/images/emoticon/emoticon10.gif


上一篇
【從面試題學邏輯-24】 如何製作能馬上找到最小值的stack?(leetcode 155. Min Stack)
下一篇
【從面試題學邏輯-26】在不使用遞迴的情況下後序走訪二元樹(leetcode 145. Binary Tree Postorder Traversal)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言