精华内容
下载资源
问答
  • 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 2.代码展示 /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode ...

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

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

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

    2.代码展示

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    int treedeep(struct TreeNode* root)
    {  
        if (root == NULL)
        {
            return 0;
        }
        int a = 1+treedeep(root->left);
        int b = 1+treedeep(root->right);
        return a>b ?a:b;
    }
    void max(int*p1,int*p2)
    {
        if (*p2>*p1)
        {
            int tmp = *p2;
            *p2 = *p1;
            *p1 = tmp;
        }
    }
    bool isBalanced(struct TreeNode* root)
    {
        if (root == NULL)
        {
            return true;
        }
        int a =  treedeep(root->left);
        int b =  treedeep(root->right);
        max(&a,&b);
        return (a-b <= 1)&&isBalanced(root->left)&&isBalanced(root->right);
    }
    

    3.解题思路
    先判断根节点是否为空,为空就遍历它的左右子树,求出左右子树的长度,然后看是否满足条件,满足就继续向下遍历,直到输出。

    展开全文
  • 一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两 个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,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 。

    代码如下:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        //判断树是否相同
        public int maxDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
            int left1 = maxDepth(root.left);
            int right1 = maxDepth(root.right);
            return Math.max(left1,right1) + 1;
        }
        
        //判断树是否为平衡二叉树
        public boolean isBalanced(TreeNode root) {
            if(root == null){
                return true;
            }else{
                int nums1 = maxDepth(root.left);
                int nums2 = maxDepth(root.right);
                int nums3 = nums1 - nums2;
                if(nums3 * nums3 < 2){
    	//当前树是否平衡
                    return isBalanced(root.left) && isBalanced(root.right);
                }else{
                    return false;
                }
            }
        }
    }

     

    展开全文
  • class Solution { public int maxDepth(TreeNode root) { if(root==null){ return 0; } int leftheight = maxDepth(root.left); int rightheight = maxDepth(root.right); return leftheight>...

    class Solution {
    public int maxDepth(TreeNode root) {
    if(root==null){
    return 0;
    }
    int leftheight = maxDepth(root.left);
    int rightheight = maxDepth(root.right);
    return leftheight>rightheight ? leftheight+1:rightheight+1;
    }
    public boolean isBalanced(TreeNode root) {
    if(root == null){
    return true;
    }
    if(Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1){
    return isBalanced(root.left)&&isBalanced(root.right);
    }
    return false;
    }
    }

    展开全文
  • 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。示例 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

    基本思路:

    按照平衡二叉树的定义来好了:

    • 空节点是平衡二叉树
    • 如果一个节点左右子树高度差不超过1,且左右子树均为平衡二叉树,那么该节点也是平衡二叉树。

    对高度求递归,再对定义求递归,判断一下,就出来了。

    要注意区别BST和平衡二叉树,这两个是完全不同的概念

    BST和平衡二叉树结合,形成的高度平衡的二叉搜索树,那就是一个崭新的世界。

    高度平衡的二叉搜索树可以由AVl, RBT, Treap(区分于普通的树堆)和

    AC代码:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int GetHeight(TreeNode *root) {
        // 其实这里在求节点的个数了
          // 处理特殊情况
          if (!root) return 0;
          // 获得左右子树高度
          int left_height = 0;
          int right_height = 0;
          if (root->left) left_height = GetHeight(root->left);
          if (root->right) right_height = GetHeight(root->right);
          // 取最大的为深度
          return max(left_height, right_height) + 1;
        }
        bool isBalanced(TreeNode* root) {
          if (!root) return true;
          int left_height = GetHeight(root->left);
          int right_height = GetHeight(root->right);
          // 不仅左右子树高度差为1, 而且左右子树必须都是平衡树
          if (fabs(left_height - right_height) <= 1 && isBalanced(root->left) && isBalanced(root->right))
            return true;
          return false;
        }
    };

    改进思路:

    之前的代码在求深度和遍历平衡二叉树的过程中重复了。

    不妨在求平衡二叉树的深度的时候引入一个flag,如果子树不是平衡二叉树就变为false;

    这里是用了-1代替false;在返回合理的值时候做一个判断,然后继续把-1往上穿

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if(root == NULL)
                return 0;
            int left = maxDepth(root->left);
            int right = maxDepth(root->right);
            if(abs(left- right)>1 || left == -1 || right == -1)
                return -1;
            return max(left, right) + 1;
        }
        bool isBalanced(TreeNode* root) {
            if(root == NULL)
                return true;
            return maxDepth(root) != -1;
        }
    };

    其他经验:

    在一个函数中其实完全可以把传值和判断一体化

    做法就是传一个不合法的值作为判断。

    每次穿合法的值的时候判断一下是否合法,不合法的话继续传递不合法的值。

    展开全文
  • 平衡二叉树

    万次阅读 多人点赞 2018-08-15 17:12:47
    一、AVL树简介 AVL树的名字来源于它的发明作者G.M....平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉排序树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右子...
  • 平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。 平衡因子(bf):结点的左子树的深度减去右子树的深度...
  • 34平衡二叉树定义

    2021-01-17 14:18:10
    平衡二叉树定义:在插入和删除二叉树结点时,要保证任意结点的左右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,简称AVL树 因此,平衡二叉树定义为一颗空树或者具有下列性质的二叉树:它的左子树...
  • 1、平衡二叉树定义:平衡二叉树(Balanced Binary Tree或Height-Balanced Tree)又称AVL树。它或者是一颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不...
  • 本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。示例 1:给定二叉树 [3,9,20,null,null,15,7]3/ 9 20/ 15 7返回 true 。示例 2:给定二叉树 [1,2,2,3,3,null,null,...
  • 平衡二叉树定义

    千次阅读 2019-05-09 21:07:29
    平衡二叉树又称AVL树,它的插入语、删除、查找操作均可在O(log n)的时间内完成。 1. AVL树或者是一棵空树,或者是具有下列性质的非空二叉搜索树: (1) 任一结点的左、右子树均为AVL树 (2) 根结点左、右子树高度差...
  • 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。 示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:true 示例 2: 输入:root = [1,2,2,3,3,null,null...
  • 本题高度平衡二叉树定义:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例1:给定二叉树[3,9,20,null,null,15,7],返回true 3 / 9 20 / 15 7示例2:给定二叉树[1,2,2,3,3,null,null,4,4],返回false...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,269
精华内容 1,307
关键字:

平衡二叉树定义