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

2019-5-7 星期二  开始吧

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

题目描述

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

题目分析

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

/**
 * 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;
    }
}

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

题目分析

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

/**
 * 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