Leetcode基础刷题之PHP解析(108,513)


2019-5-7 期二  


Leetcode基础刷题之PHP解析(98. Validate Binary Search Tree)

411982159e40f89ef2425ad4b3a8da40.png

给定一个升序的数组,转换为高度平衡的二叉查找树。

因为二叉查找树的中序遍历就是一个升序的数组,所以对于升序数组来说,我们只要找到它的中间点,就是二叉查找树的根,那么它的左右子树必然也是这个道理。

/**
 * 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 Integer[] $nums
     * @return TreeNode
     */
    function sortedArrayToBST($nums) {
        return $this->buildTree($nums,0,count($nums)-1);
    }
    
    function buildTree($nums,$l,$r){
        if($l>$r){
            return ;
        }
        $middle=floor(($l+$r)/2);
        $node=new TreeNode($nums[$middle]);
        $node->left=$this->buildTree($nums,$l,$middle-1);
        $node->right=$this->buildTree($nums,$middle+1,$r);
        return $node;
    }
}

898119923a64f1b4dde7e239731a15d2.png


给定一个二叉树,找出树最后一层最左边的结点值。

使用层进行遍历,每个层从右往左遍历,这样就能保证我们最后输出的一定是 最后一层的最左结点。

/**
 * 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 findBottomLeftValue($root) {
        $data=[];
        array_unshift($data,$root);
        while(!empty($data)){
            $node=array_shift($data);
            if($node->right !=null) array_push($data,$node->right);
            if($node->left !=null) array_push($data,$node->left);
        }
        return $node->val;
        
    }
}

树的题目到这里告一段落了

Github整理地址:https://github.com/wuqinqiang/leetcode-php


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D54 937. Reorder Log Files

>> 下一篇: Leetcode PHP题解--D55 429. N-ary Tree Level Order Traversal