算法练习之将有序数组转换为二叉搜索树,平衡二叉树详解编程语言

示例: 
 
给定有序数组: [-10,-3,0,5,9], 
 
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 
 
      0 
     / / 
   -3   9 
   /   / 
 -10  5

/** 
 * Definition for a binary tree node. 
 * public class TreeNode { 
 *     int val; 
 *     TreeNode left; 
 *     TreeNode right; 
 *     TreeNode(int x) { val = x; } 
 * } 
 */ 
class Solution { 
    public TreeNode sortedArrayToBST(int[] nums) { 
        return nums==null?null:buildTree(nums,0,nums.length-1); 
    } 
 
    public TreeNode buildTree(int[] nums,int l,int r){ 
        if(l>r) return null; 
        int m = l+(r-l)/2; 
        TreeNode root = new TreeNode(nums[m]); 
        root.left = buildTree(nums,l,m-1); 
        root.right = buildTree(nums,m+1,r); 
        return root; 
    } 
}

/** 
 * 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 empty($nums)?null:$this->buildTree($nums,0,count($nums)-1); 
    } 
     
    function buildTree($nums,$l,$r){ 
        if($l>$r) return null; 
        $m = $l+(int)(($r-$l)/2); 
        $root = new TreeNode($nums[$m]); 
        $root->left = $this->buildTree($nums,$l,$m-1); 
        $root->right = $this->buildTree($nums,$m+1,$r); 
        return $root; 
    } 
}

示例 1: 
给定二叉树 [3,9,20,null,null,15,7] 
    3 
   / / 
  9  20 
    /  / 
   15   7 
返回 true  
 
示例 2: 
给定二叉树 [1,2,2,3,3,null,null,4,4] 
       1 
      / / 
     2   2 
    / / 
   3   3 
  / / 
 4   4 
返回 false 

/** 
 * Definition for a binary tree node. 
 * public class TreeNode { 
 *     int val; 
 *     TreeNode left; 
 *     TreeNode right; 
 *     TreeNode(int x) { val = x; } 
 * } 
 */ 
class Solution { 
     public boolean isBalanced(TreeNode root) { 
 
        if(maxDepth(root)<2) return true; 
        if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1){ 
            return false; 
        }else{ 
            return isBalanced(root.left)&&isBalanced(root.right); 
        } 
    } 
 
    public int maxDepth(TreeNode root) { 
 
        return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1; 
    } 
}

/** 
 * 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 Boolean 
     */ 
    function isBalanced($root) { 
        if($this->maxDepth($root)<2) return true; 
        if(abs($this->maxDepth($root->left)-$this->maxDepth($root->right))>1){ 
            return false; 
        }else{ 
            return $this->isBalanced($root->left)&&$this->isBalanced($root->right); 
        } 
    } 
     
    function maxDepth($root){ 
        return $root==null?0:max($this->maxDepth($root->left),$this->maxDepth($root->right))+1; 
    } 
}