<?php

function getMsectime() {
    list($msec, $sec) = explode(' ', microtime());
    return (float)sprintf('%.0f', (floatval($msec) + floatval($sec)) * 1000);
}

/**
 * 节点类
 */
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;
    }
} 

/**
 * 二叉搜索树
 * 
 * 1. 若它的左树不为空，则左树上所有节点的值均小于它的根节点的值
 * 2. 若它的右树不为空，则右树上所有节点的值均大于它的根节点的值
 * 3. 它的左树、右树也分别为二叉排序树
 * 
 * 平衡二叉搜索树
 * 1. 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
 * 2. 它的左右两个子树都是一棵平衡二叉树
 * 
 * 中为根节点
 * 前序遍历：中左右
 * 中序遍历：左中右
 * 后序遍历：左右中
 * 
 */
class BinaryTree
{
    public $root;
    public $queue;
    public $index = 0;

    public function __construct(array $data)
    {
        $this->createTree($data);
    }

    public function createTree($arr) 
    {
        if (empty($arr)) {
            return null;
        }

        $this->root = new TreeNode($arr[$this->index]);
        $this->queue = new SplQueue;
        $this->queue->enqueue($this->root);

        $len = count($arr);
        while ($this->queue->count() > 0) {
            $cur = $this->queue->dequeue();
            // 左节点
            $this->index++;
            if ($this->index >= $len) {
                $this->index--;
                break;
            };
            if ($arr[$this->index] !== null) {
                $cur->left = new TreeNode($arr[$this->index]);
                $this->queue->enqueue($cur->left);
            }

            // 右节点
            $this->index++;
            if ($this->index >= $len) {
                $this->index--;
                break;
            };
            if ($arr[$this->index] !== null) {
                $cur->right = new TreeNode($arr[$this->index]);
                $this->queue->enqueue($cur->right);
            }
        }

        return $this->root;
    }
}

/**
 * 链表类
 */
class LinkedList
{
    function __construct()
    {
        // code...
    }
}

class Solution {

    /**
     * 144. 二叉树的前序遍历-DLR
     * 
     * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
     * 
     * @param TreeNode $root
     * @return Integer[]
     */
    function preorderTraversal($root) {
        // 无脑递归法
        // return $this->traversal($root);
        // 迭代法
        return $this->iterateTravsal($root);
    }

    function traversal($node, $result = []) {
        if ($node->val === null) return $result;
        $result[] = $node->val;
        $result = $this->traversal($node->left, $result);
        $result = $this->traversal($node->right, $result);
        return $result;
    }

    function iterateTravsal($node) {
        $result = [];
        $stack = new SplStack;
        $stack->push($node);
        while (!$stack->isEmpty()) {
            $cur = $stack->pop();
            $result[] = $cur->val;
            // 右节点先入栈
            if ($cur->right) {
                $stack->push($cur->right);
            }
            // 左节点后入栈（因为后入先出，下一个循环要左节点先出）
            if ($cur->left) {
                $stack->push($cur->left);
            }
        }
        return $result;
    }

    /**
     * 中序遍历-LDR
     * 
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversal($root) {
        $result = [];
        $stack = new SplStack;
        $cur = $root;
        while ($cur !== null || !$stack->isEmpty()) {
            if ($cur !== null) {
                $stack->push($cur); // 当前有效节点存入栈
                $cur = $cur->left;  // 如果左节点不是NULL继续往下找
            } else {
                // 遍历左节点到底层了
                $cur = $stack->pop();
                $result[] = $cur->val; // 中间节点
                $cur = $cur->right;
            }
        }

        return $result;
    }

    /**
     * 145. 二叉树的后序遍历-LRD
     * 
     * @param TreeNode $root
     * @return Integer[]
     */
    function postorderTraversal($root) {
        $result = [];
        $stack = new SplStack;
        $stack->push($root);
        while (!$stack->isEmpty()) {
            $cur = $stack->pop();
            $result[] = $cur->val;
            // 左节点先入栈
            if ($cur->left) {
                $stack->push($cur->left);
            }
            // 右节点后入栈（因为后入先出，下一个循环要右节点先出）
            if ($cur->right) {
                $stack->push($cur->right);
            }
        }

        return array_reverse($result);
    }
}

echo "<pre>";

// $node = new TreeNode(1, null, new TreeNode(2, 3));

// print_r(new BinaryTree([1,2,3,4,5,6]));exit;
// print_r(new BinaryTree([26,16,22,1,13,6,8]));

$time1 = getMsectime();
$solution = new Solution;

// $tree = new BinaryTree([1,null,2,3]);
$tree = new BinaryTree([3,1,2]);

print_r($solution->preorderTraversal($tree->root));
print_r($solution->inorderTraversal($tree->root));
print_r($solution->postorderTraversal($tree->root));

$time2 = getMsectime();

$result = (is_object($result) || is_array($result)) ? json_encode($result) : $result;
// echo $solution->nums."次<br>";
// echo '<br>结果：'.implode(',', $result1)."<br>", '执行耗时：'.($time2 - $time1)."ms";
echo '<br>结果：'.$result."<br>", '执行耗时：'.($time2 - $time1)."ms";