2020-06-07-PHP 实现计算二叉树深度及前中后序遍历二叉树

layout: posttitle: PHP 实现计算二叉树深度及前中后序遍历二叉树
subtitle: PHP 实现计算二叉树深度及前中后序遍历二叉树
date: 2020-06-07
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 二叉树深度
- 前中后序遍历
- 递归
- 迭代

计算二叉树深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

提示：

节点总数 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof

直接递归左边，再递归右边，比较两个深度的最大值即可，最终需要加一，因为根也算是一个深度。
php 代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxDepth($root) {
        if ($root == null) {
            return 0;
        }
        $leftDepth = $this->maxDepth($root->left);
        $rightDepth = $this->maxDepth($root->right);
        return max($leftDepth, $rightDepth) + 1;
    }
}

二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
输出: [1,2,3]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal

递归实现太简单了，此次用迭代实现，借助 array_push 不断将数据插入数组尾部，然后优先判断右边的数据，不为空则压入栈，先进后出，则相当于还是先读取左子树数据（先压左边数据的话，可以使用队列，效果一样）。

PHP 代码：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function preorderTraversal($root) {
        $s = new SplStack();
        $s->push($root);
        $result = [];
        while(!$s->isEmpty()) {
            $data = $s->pop();
            array_push($result, $data->val);
            if ($data->right != null) {
                $s->push($data->right);
            }
            if ($data->left != null) {
                $s->push($data->left);
            }
        }
        return $result;
    }
}

二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
输出: [3,2,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal

递归实现太简单了，此次用迭代实现，借助 array_unshift 不断将数据插入数组头部，然后优先判断左边的数据，不为空则压入栈，先进后出，则相当于还是先读取右子树数据。

PHP 实现

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function postorderTraversal($root) {
        $s = new SplStack();
        $s->push($root);
        $result = [];
        while(!$s->isEmpty()) {
            $data = $s->pop();
            array_unshift($result, $data->val);
            if ($data->left != null) {
                $s->push($data->left);
            }
            if ($data->right != null) {
                $s->push($data->right);
            }
        }
        return $result;
    }
}

二叉树的中序遍历

给定一个二叉树，返回它的中序遍历结果。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal

主要先向左走到头，弹出栈顶元素，向右跳一步，再重复上述步骤，顺序是左中右的处理。

PHP 实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversal($root) {
        $stack = new SplStack();
        $result = [];
        $pNode = $root;
        while ($pNode !== null || !$stack->isEmpty()) {
            if ($pNode !== null) {
                $stack->push($pNode);
                $pNode = $pNode->left;
            } else {
                $node = $stack->pop();
                $result[] = $node->val;
                $pNode = $node->right;
            }
        }
        return $result;
    }
}

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券