Published in
Jul 15, 2023
# 前言
藉由 LeetCode 磨練演算法
# 正文
- 思路: preorder 的順序是
中, 左, 右
, 所以照著這個順序來遞迴就行了 - 複雜度: 時間複雜度
O(n)
, 空間複雜度O(n)
- 題目連結
- solution example 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) {
$res = [];
$this->traverse($root, $res);
return $res;
}
function traverse($node, &$res) {
if (is_null($node)) {
return;
}
$res[] = $node->val;
$this->traverse($node->left, $res);
$this->traverse($node->right, $res);
}
}