精华内容
下载资源
问答
  • 2021-04-14 17:32:51

    - 题目描述:
    输入一棵二叉树,判断该二叉树是否是平衡二叉树。
    在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
    平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    - 示例:
    输入:
    {1,2,3,4,5,6,7}
    输出:
    true

    - 思路分析:
    本题很容易想到的第一个想法就是采用递归的方法从二叉树的根节点自上而下遍历,再配合上左右子树高度差小于等于1和左右子树都是平衡二叉树这两个判断条件,就可以将本提解决。
    - 实现代码:

    public class Solution {
        public boolean IsBalanced_Solution(TreeNode root) {
            if(root == null)
                return true;
            return Math.abs(depth(root.left) - depth(root.right)) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        }
        public int depth(TreeNode root){
            int maxdepth;
            if(root == null)
                return 0;
            else{
                maxdepth = Math.max(depth(root.left), depth(root.right)) + 1;
                return maxdepth;
            }
        }
    }
    

    - 改进优化:
    上述自上向下的遍历方式明显存在缺陷,就是时间开销过大,需要将所有结点遍历一遍才可以判断高度差和左右子树是否为平衡二叉树。如果改为从下往上遍历,如果子树是平衡二叉树,则返回子树的高度;如果发现子树不是平衡二叉树,则直接停止遍历,这样至多只对每个结点访问一次。

    public class Solution {
        public boolean IsBalanced_Solution(TreeNode root) {
            return getDepth(root) != -1;
        }
         
        public int getDepth(TreeNode root) {
            if (root == null) return 0;
            int left = getDepth(root.left);
            if (left == -1) return -1;
            int right = getDepth(root.right);
            if (right == -1) return -1;
            return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
        }
    }
    
    更多相关内容
  • 平衡二叉树专题

    千次阅读 2021-02-12 02:06:04
    力扣关于平衡二叉树的题目还是有一些的,并且都非常经典,推荐大家练习。今天给大家精选了 4 道题,如果你彻底搞明白了这几道题,碰到其他的平衡二叉树的题目应该不至于没有思路。当你领会了我的思路之后, 建议再找...

    力扣关于平衡二叉树的题目还是有一些的,并且都非常经典,推荐大家练习。今天给大家精选了 4 道题,如果你彻底搞明白了这几道题,碰到其他的平衡二叉树的题目应该不至于没有思路。当你领会了我的思路之后, 建议再找几个题目练手,巩固一下学习成果。

    110. 平衡二叉树(简单)

    最简单的莫过于判断一个树是否为平衡二叉树了,我们来看下。

    题目描述

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

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

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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。用伪代码描述就是:

    if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是平衡二叉树 and root.right 也是平衡二叉树:

    print('是平衡二叉树')

    else:

    print('不是平衡二叉树')

    而 root.left 和 root.right 如何判断是否是二叉平衡树就和 root 是一样的了,可以看出这个问题有明显的递归性。

    因此我们首先需要知道如何计算一个子树的高度。这个可以通过递归的方式轻松地计算出来。计算子树高度的 Python 代码如下:

    def dfs(node, depth):

    if not node: return 0

    l = dfs(node.left, depth + 1)

    r = dfs(node.right, depth + 1)

    return max(l, r) + 1

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:

    def isBalanced(self, root: TreeNode) -> bool:

    def dfs(node, depth):

    if not node: return 0

    l = dfs(node.left, depth + 1)

    r = dfs(node.right, depth + 1)

    return max(l, r) + 1

    if not root: return True

    if abs(dfs(root.left, 0) - dfs(root.right, 0)) > 1: return False

    return self.isBalanced(root.left) and self.isBalanced(root.right)

    复杂度分析

    时间复杂度:对于 isBalanced 来说,由于每个节点最多被访问一次,这部分的时间复杂度为 $O(N)$,而 dfs 函数 每次被调用的次数不超过 $log N$,因此总的时间复杂度为 $O(NlogN)$,其中 $N$ 为 树的节点总数。

    空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为 $O(h)$,其中 $h$ 为树的高度。

    108. 将有序数组转换为二叉搜索树(简单)

    108 和 109 基本是一样的,只不过数据结构不一样,109 变成了链表了而已。由于链表操作比数组需要考虑更多的因素,因此 109 是 中等难度。

    题目描述

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

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

    示例:

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

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

    0

    / \

    -3 9

    / /

    -10 5

    思路

    对于这个问题或者 给定一个二叉搜索树,将其改为平衡(后面会讲) 基本思路都是一样的。

    题目的要求是将有序数组转化为:

    高度平衡的二叉树

    二叉搜索树

    由于平衡二叉树是左右两个子树的高度差的绝对值不超过 1。因此一种简单的方法是选择中点作为根节点,根节点左侧的作为左子树,右侧的作为右子树即可。原因很简单,这样分配可以保证左右子树的节点数目差不超过 1。因此高度差自然也不会超过 1 了。

    上面的操作同时也满足了二叉搜索树,原因就是题目给的数组是有序的。

    你也可以选择别的数作为根节点,而不是中点,这也可以看出答案是不唯一的。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:

    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

    if not nums: return None

    mid = (len(nums) - 1) // 2

    root = TreeNode(nums[mid])

    root.left = self.sortedArrayToBST(nums[:mid])

    root.right = self.sortedArrayToBST(nums[mid + 1:])

    return root

    复杂度分析

    时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为 $O(N)$,其中 $N$ 为数组长度。

    空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为 $O(h)$,其中 $h$ 为树的高度。同时由于是平衡二叉树,因此 $h$ 就是 $log N$。

    109. 有序链表转换二叉搜索树(中等)

    题目描述

    `给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

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

    示例:

    给定的有序链表: [-10, -3, 0, 5, 9],

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

    0

    / \

    -3 9

    / /

    -10 5

    思路

    和 108 思路一样。 不同的是数据结构的不同,因此我们需要关注的是链表和数组的操作差异。

    417f4a08024c444b43c4aca75073f099.png

    (数组的情况)

    我们再来看下链表:

    8ec5e2235093c589bb2cb7eeab028b79.png

    (链表的情况)

    找到中点,只需要使用经典的快慢指针即可。同时为了防止环的出现, 我们需要斩断指向 mid 的 next 指针,因此需要记录一下中点前的一个节点,这只需要用一个变量 pre 记录即可。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:

    def sortedListToBST(self, head: ListNode) -> TreeNode:

    if not head:

    return head

    pre, slow, fast = None, head, head

    while fast and fast.next:

    fast = fast.next.next

    pre = slow

    slow = slow.next

    if pre:

    pre.next = None

    node = TreeNode(slow.val)

    if slow == fast:

    return node

    node.left = self.sortedListToBST(head)

    node.right = self.sortedListToBST(slow.next)

    return node

    复杂度分析

    时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为 $O(N)$,其中 $N$ 为链表长度。

    空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为 $O(h)$,其中 $h$ 为树的高度。同时由于是平衡二叉树,因此 $h$ 就是 $log N$。

    1382. 将二叉搜索树变平衡(中等)

    题目描述

    给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。

    如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。

    如果有多种构造方法,请你返回任意一种。

    示例:

    199e0219f41fca7db5dcdabed903baa9.png

    输入:root = [1,null,2,null,3,null,4,null,null]

    输出:[2,1,3,null,null,null,4]

    解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。

    提示:

    树节点的数目在 1 到 10^4 之间。

    树节点的值互不相同,且在 1 到 10^5 之间。

    思路

    由于二叉搜索树的中序遍历是一个有序数组,因此问题很容易就转化为 108. 将有序数组转换为二叉搜索树(简单)。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:

    def inorder(self, node):

    if not node: return []

    return self.inorder(node.left) + [node.val] + self.inorder(node.right)

    def balanceBST(self, root: TreeNode) -> TreeNode:

    nums = self.inorder(root)

    def dfs(start, end):

    if start == end: return TreeNode(nums[start])

    if start > end: return None

    mid = (start + end) // 2

    root = TreeNode(nums[mid])

    root.left = dfs(start, mid - 1)

    root.right = dfs(mid + 1, end)

    return root

    return dfs(0, len(nums) - 1)

    复杂度分析

    时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为 $O(N)$,其中 $N$ 为链表长度。

    空间复杂度:虽然使用了递归,但是瓶颈不在栈空间,而是开辟的长度为 $N$ 的 nums 数组,因此空间复杂度为 $O(N)$,其中 $N$ 为树的节点总数。

    总结

    本文通过四道关于二叉平衡树的题帮助大家识别此类型题目背后的思维逻辑,我们来总结一下学到的知识。

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

    如果需要让你判断一个树是否是平衡二叉树,只需要死扣定义,然后用递归即可轻松解决。

    如果需要你将一个数组或者链表(逻辑上都是线性的数据结构)转化为平衡二叉树,只需要随便选一个节点,并分配一半到左子树,另一半到右子树即可。

    同时,如果要求你转化为平衡二叉搜索树,则可以选择排序数组(或链表)的中点,左边的元素为左子树, 右边的元素为右子树即可。

    小提示 1: 如果不需要是二叉搜索树则不需要排序,否则需要排序。

    小提示 2: 你也可以不选择中点, 算法需要相应调整,感兴趣的同学可以试试。

    小提示 3: 链表的操作需要特别注意环的存在。

    展开全文
  • 平衡二叉树习题

    千次阅读 2020-05-18 09:56:40
    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 ...

    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 。

    class Solution {
        public boolean isBalanced(TreeNode root) {
            return recur(root) != -1;
        }
    
        private int recur(TreeNode root) {
            if (root == null) return 0;
            int left = recur(root.left);
            if(left == -1) return -1;
            int right = recur(root.right);
            if(right == -1) return -1;
            return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
        }
    }
    
    
    
    class Solution {
    private:
      // Recursively obtain the height of a tree. An empty tree has -1 height
      int height(TreeNode* root) { 
        // An empty tree has height -1
        if (root == NULL) {
          return -1;
        }
        return 1 + max(height(root->left), height(root->right));
      }
    public:
      bool isBalanced(TreeNode* root) {
        // An empty tree satisfies the definition of a balanced tree
        if (root == NULL) {
          return true;
        }
    
        // Check if subtrees have height within 1. If they do, check if the
        // subtrees are balanced
        return abs(height(root->left) - height(root->right)) < 2 &&
          isBalanced(root->left) &&
          isBalanced(root->right);
      }
    };
    
    展开全文
  • 平衡二叉树详解

    千次阅读 2022-03-27 14:52:47
    一、平衡二叉树 平衡二叉搜索树又被称为AVL树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树平衡二叉树的常用实现方法有红黑树、AVL等。 二、...

    一、平衡二叉树

    平衡二叉搜索树又被称为AVL树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL等。

    二、作用

    我们有时在编程过程中可能会需要用到链表(时间复杂度O(n))来进行对数据的存储,但是当数据量变得十分庞大时我们对于指定数据的一些操作的时间消耗就会变得大,这时我们就需要借助将链表的结构变为二叉搜索树(时间复杂度O(logn))来进行数据的存储。
    但在某些情况下,例如:对[1,2,3,4,5,6,…]这种其中含有大量有序部分的数组构造二叉搜索树,这会使二叉搜索树类似于链表,这会使对于数据的一些操作的时间复杂度增大到O(n)。
    所以一般的二叉搜索树在进行数据的存储时可能会使工作的时间复杂度并未降低太多,这时便需要我们将二叉树的高度尽可能的降低,使二叉树的高度降低为log(n),这样我们就得到了一个高度平衡的二叉搜索树,使对于数据的一系列操作的时间复杂度稳定在O(logn)。

    三、构造平衡二叉树

    1、递归

    我们可以将需要被构造的数组排序,然后不断从数组的中心递归来构造二叉树。
    (参考 力扣1382.将二叉搜索树变平衡)

    class Solution {
    public:
        vector<int> inorderSeq;
        
        //将二叉搜索树中的数据通过中序遍历变为有序数组
        void getInorder(TreeNode* o) {
            if (o->left) {
                getInorder(o->left);
            }
            inorderSeq.push_back(o->val);
            if (o->right) {
                getInorder(o->right);
            }
        }
    
        //优先构建数组中心的结点
        TreeNode* build(int l, int r) {
            int mid = (l + r) >> 1;//中心位置
            TreeNode* o = new TreeNode(inorderSeq[mid]);
            if (l <= mid - 1) {
                o->left = build(l, mid - 1);//构建中心结点的左子树
            }
            if (mid + 1 <= r) {
                o->right = build(mid + 1, r);//构建中心节点的右子树
            }
            return o;
        }
    
        TreeNode* balanceBST(TreeNode* root) {
            getInorder(root);
            return build(0, inorderSeq.size() - 1);
        }
    };
    

    以上方法逻辑简单,但作用于二叉搜索树,其数据本身具有有序性,若对于一组无序的数据,这种方法显然行不通的。
    那么我们需要另一种方法来满足一边构造结点,一边检查树是否平衡,一边对数的结构进行优化。

    2、旋转

    右旋转:

    在这里插入图片描述
    如图,对于一个二叉树的结点我们用其左子树的高度减去其右子树的高度并标记在结点之上,我们这里将其称为高度因子。例如3结点的左子树的高度为2,右子树的高度为1,所以我们将数字1标记在3结点上方。
    我们要在此平衡二叉搜索树中插入结点0。
    在这里插入图片描述
    如图,插入0结点后二叉树的平衡被破坏,以结点3和以结点2为根节点的二叉树的高度因子都变为2,显然当高度因子的绝对值大于1时,以该结点为根节点的二叉树是不平衡的,对于这种情况我们只需要把二叉树中高度最小的不平衡子树进行旋转操作,使其高度减一,这样该结点的所有祖先结点的高度因子全部减一,使所有的结点的高度因子的绝对值都不超过1,使二叉树达到平衡。
    对于图中的情况,我们只需要对以2结点为根节点的子树进行旋转即可。
    在这里插入图片描述
    这种出现连续左子树的不平衡的二叉树我们成称LL型,在代码中可以通过高度因子的正负来判断不平衡最小二叉树的类型,需要将该二叉树像图中一样旋转,称为右旋转。
    在这里插入图片描述
    经过旋转之后二叉树的3结点的左子树变为1,1的右子树变为2。
    二叉树恢复平衡。

    LL旋转(右旋转)伪代码:

    在这里插入图片描述

    //A为最低不平衡结点,B为A的左节点
    AVLTree* RightRotation(Node *A)
    { /* 注意:A必须有一个左子结点B */
      /* 将A与B做右单旋,更新A与B的高度,返回新的根结点B */
        Node *B = A->Left;
        A->Left = B->Right;
        B->Right = A;
        A->Height = max(GetHeight(A->Left), GetHeight(A->Right)) + 1;//A更新高度
        B->Height = max(GetHeight(B->Left), A->Height) + 1;//B更新高度
        return B;//返回新的子树根节点,与父亲结点连接
    }
    

    左旋转:

    在这里插入图片描述
    如图,在图中的平衡二叉搜索树中插入5结点。
    在这里插入图片描述
    对于图中情况与右旋转正好相反,只需要对最小不平衡树(以3为根节点的二叉树)进行旋转,旋转后2结点的右子结点为4结点,3结点成为4结点的左子结点。旋转后如下。
    在这里插入图片描述

    RR旋转(左旋转)伪代码:

    在这里插入图片描述

    //A为最低不平衡结点,B为A的右节点
    AVLTree* LeftRotation(Node *A)
    { /* 注意:A必须有一个右子结点B */
      /* 将A与B做左旋转,更新A与B的高度,返回新的根结点B */
        Node *B = A->Right;
        A->Right = B->Left;
        B->Left = A;    
        /*GetHeight为获取高度的函数*/
        A->Height = max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
        B->Height = max(GetHeight(B->Left),A->Height) + 1;
        return B;//返回新的子树根节点,与父亲结点连接
    }
    

    右左双旋转:

    在这里插入图片描述
    如图,我们要在图中的平衡二叉搜索树中插入结点2。
    在这里插入图片描述
    插入2结点后,灰色框中为最小不平衡二叉树,其不平衡是由子树根节点的右子树和右子树的左子树引起(在代码中由根节点和左子结点的高度因子判断),这种情况我们定义为RL型,因为是1的右子树的左子树引起的不平衡,需要先对这里的3结点进行右旋转使其变成RR型,再对1结点进行左旋转使其平衡。过程如下:
    在这里插入图片描述

    第一次3结点右旋转后,2结点成为1结点的右子结点,3结点成为2结点的右子结点,此时的二叉树为RR型,再将1结点左旋转1结点成为2结点的左子结点,最开始连结1结点的4结点此时连结2结点,这时二叉树平衡。
    在这里插入图片描述

    RL旋转(右左双旋转)伪代码:

    AVLTree* RightLeftRotation(Node *A)
    { 
       Node* B = A->Left;
        A->Left = SingriRightRotation(B);//先对B结点右旋转,将A转化为RR
        return SingleLeftRotation(A);//先对A结点左旋转
    }
    

    在这里插入图片描述
    如图,我们要在图中的平衡二叉搜索树中插入结点4。
    在这里插入图片描述
    插入4结点后,灰色框中为最小不平衡二叉树,其不平衡是由5节点的左子树和左子树的右子树引起(在代码中由根节点和左子结点的高度因子判断),这种情况我们定义为LR型,需要先对这里的3结点进行左旋转使其变成LL型,再对5结点进行右旋转使其平衡。过程如下:
    在这里插入图片描述第一次3结点左旋转后,4结点成为5结点的左子结点,3结点成为4结点的左子结点,此时的二叉树为LL型,再将5结点右旋转5结点成为4结点的右子结点,最开始连结5结点的2结点此时连结4结点,这时二叉树平衡。
    在这里插入图片描述

    AVLTree* LeftRightRotation(Node *A)
    { 
        Node* B = A->Left;
        A->Left = SingriLeftRotation(B);//先对B结点左旋转,将A转化为LL
        return SingleRightRotation(A);//再对A结点右旋转
    }
    

    添加新结点:

    void UpdateHeight(Node *rt){	//更新高度  	
        if(rt==NULL)	 return; 
        rt->height=max(GetHeight(rt->left),GetHeight(rt->right))+1;
    }
    
    bool InsertBST(Node *rt, int k){		//插入 
    	if(rt==NULL){
    		rt=new Node(k);
    		return true;
    	}
    	if(k==rt->val)	return false;
    	bool res=true;//判断插入是否成功
    	if(k<rt->val){
    		res=InsertBST(rt->left,k);
    		if(res&&GetHeight(rt->left)-GetHeight(rt->right)>1){
    			if(k<rt->left->val)	LeftRotation(rt);	//左左
    			else	LeftRightRotation(rt);			//左右 
    		}
    	}else{
    		res=InsertBST(rt->right,k);
    		if(res&&GetHeight(rt->left)-GetHeight(rt->right)<-1){
    			if(k>rt->right->val)	RightRotation(rt);	//右右 
    			else	RightLeftRotation(rt);		        //右左 
    		}
    	}
    	if(res) UpdateHeight(rt);//高度更新
    	return res;
    }
    

    删除结点:

    void DeleteBST_(Node *rt, Node *pt){        //删除节点有左右子树时处理 
        if(rt->right==NULL){
            Node *p=rt;
            pt->val=rt->val;
            rt=rt->left;
            delete p;
        }else
        {
            DeleteBST_(rt->right,pt);
            if(GetHeight(rt->left)-GetHeight(rt->right)>1){
                LeftRotation(rt);                   //左左 
            }
        }
        UpdateHeight(rt);
    }   
    
    bool DeleteBST(Node *rt,int k){     //删除
        if(rt==NULL)    return false;
        bool res=true;
        if(rt->val==k){
            if(rt->left==NULL){
                rt=rt->right;
            }else if(rt->right==NULL){
                rt=rt->left;
            }else{
                DeleteBST_(rt->left,rt);    
            }
        }else if(k<rt->val){
            res=DeleteBST(rt->left,k);      //向目标值递归
            if(res&&GetHeight(rt->left)-GetHeight(rt->right)>1){//成功删除后调整二叉树
                if(k<rt->left->val) LeftRotation(rt);   //左左
                else    LeftRightRotation(rt);              //左右
            }else if(res&&GetHeight(rt->left)-GetHeight(rt->right)<-1){
                if(k>rt->right->val)    RightRotation(rt);  //右右 
                else    RightLeftRotation(rt);                  //右左 
            }
        }else{
            res=DeleteBST(rt->right,k);     //向目标值递归
            if(res&&GetHeight(rt->left)-GetHeight(rt->right)>1){//成功删除后调整二叉树
                if(k<rt->left->val) LeftRotation(rt);   //左左
                else    LeftRightRotation(rt);              //左右 
            }else if(res&&GetHeight(rt->left)-GetHeight(rt->right)<-1){
                if(k>rt->right->val)    RightRotation(rt);  //右右 
                else    RightLeftRotation(rt);                  //右左 
            }
        }
        if(res) UpdateHeight(rt);
        return res;
    }
    

    投稿来自 东北石油大学 - 计科206 - 赵宇昊

    展开全文
  • 题目题目:输入一棵二叉树,判断该二叉树是否是平衡二叉树。注:这个题思路很好,可以经常看。解法一思路一般来说,平衡二叉树既是平衡的树,又是二分搜索树。但此题只要求判断是不是平衡的。判断一棵树是否是平衡的...
  • 本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:true 示例 2: 输入:root = [1,2,2,3,3,null,null,...
  • 平衡二叉树的调整整理 相关概念 平衡二叉树 平衡二叉树又称AVL树,特点是它的左子树和右子树都是平衡二叉树,而且左子树和右子树的深度之差不超过1 平衡因子 二叉树结点上左子树的深度减去右子树的深度,平衡...
  • 平衡二叉树的构造过程实例

    万次阅读 多人点赞 2019-04-14 09:13:08
    平衡二叉树实现的实例 选取一组数据分别为2,1,0,3,4,5,6,9,8,7的10个结点来构造平衡二叉树。 首先数据为2的结点作为根结点插入,接着插入1,仍是平衡的,再插入0是,2的平衡因子变为2,此时出现了不平衡...
  • 平衡二叉树

    2022-04-07 19:15:35
    定义:平衡二叉树是一棵二叉排序树,或者为空,或者满足以下条件: (1)左右子树高度差的绝对值不大于1; (2)左右子树都是平衡二叉树。 平衡因子:对于二叉树中任一结点T,其平衡因子(Balance Factor,简称 BF)...
  • 现在通过实例来分析平衡二叉树的实现过程,以便更好的理解。 选取一组数据分别为2,1,0,3,4,5,6,9,8,7的10个结点来构造平衡二叉树。 (1)首先数据为2的结点作为根结点插入,接着插入1,仍是平衡的...
  • 平衡二叉树、二叉树的经典题 1 平衡二叉树 题目 输入一棵二叉树,判断该二叉树是否是平衡二叉树平衡二叉树:每个子树的深度之差不超过1 思路 后续遍历二叉树,在遍历二叉树每个节点前都会遍历其左右子树 ...
  • 二叉树相关OJ题目——二叉树的高度,平衡二叉树的判断
  • 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 示例1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 ...
  • 题目: 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。给定有序数组: [-10,-3,0,5,9]。 概念详解 1.高度平衡二叉搜索树(AVL树) (1)左子树与右子树的高度之差的绝对值不超过1。 (2)整棵树...
  • 插入值插入在叶子节点上 例题: 就是一个点一个点的加就行,加入某个点后如果失衡,则调整,调整后在加点,再调整,知道所有的点都加上,且不失衡就ok了
  • 定义: 平衡二叉树(AVL):是一种平衡的二叉搜索树。 平衡因子:将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor),|BF|。 性质: 空二叉树是一个 AVL 树 如果 T 是一棵 AVL 树...
  • 力扣题---平衡二叉树

    2022-05-01 21:10:08
    题目链接:平衡二叉树 先来看题目与例题: 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 示例 1: 输入...
  • 面试题:平衡二叉树

    2021-01-17 15:11:38
    题目描述输入一棵二叉树,判断该二叉树是否是平衡二叉树。知识点平衡二叉树Qiang的思路平衡二叉树是指一个二叉树的左子树深度相差不超过1,可以相等或相差为1。为了判断一个二叉树是不是平衡二叉树,我们只需要计算...
  • 数据结构(八)平衡二叉树

    千次阅读 多人点赞 2018-11-02 12:01:46
    平衡二叉树的定义和四种调整策略
  • 构造平衡二叉树 期末题一: 对关键字序列{23,76,47,53,41,12,85,30,90,100},构造一棵平衡二叉树并画图。 按照顺序依次插入,第一数是23,作为根节点。 第二个是76,比23大,作为23的右孩子。 第三个是47...
  • 数据结构——平衡二叉树之删除

    千次阅读 2021-07-08 08:15:25
    我们知道,在平衡二叉树中插入一个结点可能会改变二叉树的平衡因子,使得平衡因子超过1。但是删除平衡二叉树的一个结点时也会使得二叉树的平衡因子发生改变。也会需要对树进行调整。这篇博客是说明怎么判断调整位置...
  • N层平衡二叉树的画法

    2021-06-11 18:26:11
    以5层平衡二叉树为例 直接上示意图 注:下图仅为多种画法之一,只看绿色部分即可。 会搜索到这篇文章的同学,可能是因为对以下两者的概念产生了混淆: 平衡二叉树 VS 折半查找的查找判定树 两者区别在于:前者关注...
  • 常见二叉树例题汇总(更新中)
  • 平衡二叉树 描述 示例 1 示例 2 示例 3 提示 方法:递归 平衡二叉树 描述 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点的左右两个子树的...
  • 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 返回...
  • 二叉树例题

    2020-12-18 16:24:07
    二叉树的前中后层序遍历
  • OJ链接:判断一棵二叉树是否为平衡二叉树 题目描述: 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。 ...
  • 二叉树例题解析1.单值二叉树2.翻转二叉树3.相同的树4.另一个树的子树5.对称二叉树6.平衡二叉树 1.单值二叉树 如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。 bool _isUnivalTree(struct TreeNode...

空空如也

空空如也

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

平衡二叉树例题

友情链接: CU_Multitexture.rar