迭代二叉树

Class TreeNode {
    public int $val;

    public ?TreeNode $left  = null;
    public ?TreeNode $right = null;

    public function __construct(int $x)
    {
        $this->val = $x;
    }
}

Class Solution {
    public function preorderTraversal(TreeNode $root) : ?array
    {
        if (empty($root)) return [];

        $stack  = [$root];
        $output = array();

        while (boolval($stack)) {
            $root = array_pop($stack);

            if (boolval($root)) {
                array_push($output, $root->val);
                if (boolval($root->right)) {
                    array_push($stack, $root->right);
                }
                if (boolval($root->left)) {
                    array_push($stack, $root->left);
                }
            }
        }

        return $output;
    }

     public function inorderTraversal(TreeNode $root) : ?array
    {
        $stack = $output = array();
        $curr = $root;

        while (boolval($curr) || boolval($stack)) {
            while (boolval($curr)) {
                array_push($stack, $curr);
                $curr = $curr->left;
            }
            $curr = array_pop($stack);
            array_push($output, $curr->val);
            $curr = $curr->right;
        }
        return $output;
    }

    public function postorderTraversal(TreeNode $root) : ?array
    {
        if (empty($root)) return [];

        $stack  = [$root];
        $output = array();

        while (boolval($stack)) {
            $root = array_pop($stack);

            if (boolval($root)) {
                array_push($output, $root->val);
                if (boolval($root->left)) {
                    array_push($stack, $root->left);
                }
                if (boolval($root->right)) {
                    array_push($stack, $root->right);
                }
            }
        }

        return array_reverse($output);
    }
}

$first  = new TreeNode(1);
$second = new TreeNode(2);
$third  = new TreeNode(3);

$first->right = $second;
$second->left = $third;

   //     1
   //      \
   //       2
   //      /
   //     3

$solution = new Solution();

$result['pre'] = $solution->preorderTraversal($first);
$result['in'] = $solution->inorderTraversal($first);
$result['post'] = $solution->postorderTraversal($first);


print_r($result);

Array
(
    [pre] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 3
        )

    [in] => Array
        (
            [0] => 1
            [1] => 3
            [2] => 2
        )

    [post] => Array
        (
            [0] => 3
            [1] => 2
            [2] => 1
        )

)

[Process exited 0]

本作品采用《CC 协议》，转载必须注明作者和本文链接