# 前言

藉由 LeetCode 來磨練演算法

# 題目連結

Binary Tree Preorder Traversal - LeetCode

# 解題思路

# Stack

preorder 在 binary tree 中的意思，代表須依照順序 中 -> 左 -> 右 來輸出，LeetCode 的範例圖片我覺得沒有很清楚，可參考下面的示意圖，數字代表順序

graph TD
    A((1)) --L--> B[2]
    A --R--> C[7]
    B --L--> D[3]
    D --L--> D1[4]
    D1 --R--> D3[5]
    B --R--> E[6]
    C --L--> F[8]
    C --R--> G[9]
    F --R--> J[10]

Tree 的結構可以理解成是一個 Linked List，每個 node 都有其 val & left node & right node，解題目標在於 將這些 node 的 val 以 中 -> 左 -> 右 的順序放到 array 中，所以重點在於控制 node 的順序

先模擬一下 preorder 的順序，可以發現，每拿到一個 node，都會先把該 node 的 val 放到 array，然後再依照 left -> right 的順序來取得下一個 node

可以使用 Stack 的資料結構來解題，Stack 的特性是 先進後出，依照上面的邏輯，我們需要

• 每拿到一個 node，就把 val 放到 array
• 並依照 左 -> 右 的順序來處理下一個 node
• 所以只要我把 root node 放到一個 stack 中，當使用 pop 取得 node 時就把 val 放到 array，然後再依照 相反順序 將 right node -> left node 放到 Stack，這樣下一次取 node 時就會先取 left node，因為 Stack 先進後出的特性

複雜度：

• 時間複雜度為 O(N)
• 空間複雜度為 O(N)

# solution code

<?php
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function preorderTraversal($root) {
        $stack = [];
        $stack[] = $root;
        $res = [];

        while (count($stack) !== 0) {
            $node = array_pop($stack);
            $res[] = $node->val;

            if ($node->right) $stack[] = $node->right;
            if ($node->left) $stack[] = $node->left;
        }

        return $res;
    }
}