[DFS] 深度優先搜尋（Depth-First Search）

深度優先搜尋

深度優先搜尋有三種搜尋，前序、中序、後序

首先，限定樹的類別

<?php

Class TreeNode {
    public function __construct(
        public $value = 0,
        public ?TreeNode $left = null,
        public ?TreeNode $right = null
    ) {
    }
}

前序走訪

<?php 

function preorder (TreeNode $node) {
    // 最後一個節點
    if ($node == null) return;
    // 從根節點，向左讀取，直到左邊沒有東西後，才向右讀取
    echo $node->value;
    inorder($node->left);
    inorder($node->right);
}

中序走訪

<?php 

function inorder (TreeNode $node) {
    // 最後一個節點
    if ($node == null) return;
    // 從左邊最下面開始讀取，接著向上讀取一層後，再向右讀取
    inorder($node->left);
    echo $node->value;
    inorder($node->right);
}

後序走訪

<?php 

function postorder (TreeNode $node) {
    // 最後一個節點
    if ($node == null) return;
    // 從左邊最下面開始讀取左右數，接著才向上讀取一層
    inorder($node->left);
    inorder($node->right);
    echo $node->value;
}