Leetcode PHP题解--D125 107. Binary Tree Level Order Traversal II

码农天地 - 2020-10-02 12:08:04

D125 107. Binary Tree Level Order Traversal II题目链接

107. Binary Tree Level Order Traversal II

题目分析

给定一个二叉树，把同一层的值放在同一键下的数组内，以左节点的值为先，逆序返回。

思路

从给出的样例可知，越在顶层的值，它的键值越大。
左节点的值在前面，这个就简单了，用先序遍历，把值直接塞入数组末尾即可。
由于层高是不确定的，我决定先把顶层的值存在前面，最后用array_reverse倒转数据来解决。

最终代码

<?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 {
    private $vals = [];
    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrderBottom($root) {
        $this->preOrder($root, 0);
        return array_reverse($this->vals);
    }
    function preOrder($node, $level){
        if(is_null($node)){
            return;
        }
        if(!isset($this->vals[$level])){
            $this->vals[$level] = [];
        }
        $this->vals[$level][] = $node->val;
        if($node->left){
            $this->preOrder($node->left, $level+1);
        }
        if($node->right){
            $this->preOrder($node->right, $level+1);
        }
    }
}

若觉得本文章对你有用，欢迎用爱发电资助。

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。