首页 > 编程语言 > 详细

算法练习之将有序数组转换为二叉搜索树,平衡二叉树

时间:2019-05-23 15:10:24      阅读:54      评论:0      收藏:0      [点我收藏+]

标签:平衡二叉树   col   depth   uil   style   二叉搜索树   树的高度   定义   urn   

1.将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

题中,高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

      0
     /    -3   9
   /   /
 -10  5

java

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

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

2.平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

  一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

示例 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 

java

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

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

 

算法练习之将有序数组转换为二叉搜索树,平衡二叉树

标签:平衡二叉树   col   depth   uil   style   二叉搜索树   树的高度   定义   urn   

原文:https://www.cnblogs.com/baby123/p/10911820.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号