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

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

author: he xiaodong date: 2020-06-07
计算二叉树深度

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

例如:

给定二叉树 [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;
    }
}

顺带推荐买课,用右侧链接有优惠 算法面试通关40讲