精华内容
下载资源
问答
  • 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   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);
      }
    };
    
    更多相关内容
  • 平衡二叉树专题

    千次阅读 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: 链表的操作需要特别注意环的存在。

    展开全文
  • 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 示例1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 ...

    1 题目描述

    输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 <= 树的结点个数 <= 10000
    

    2 解题思路

    2.1 方法1:后序遍历+剪枝(从底至顶)(最优解法)

    思路是对二叉树做后序遍历,从底至顶返回子树深度,若判定某子树不是平衡树则 “剪枝” ,直接向上返回。

    算法流程:
    recur(root)函数:

    • 返回值:
      • 当节点root左/右子树的深度差小于等于1:则返回当前子树的深度,即节点root的左/右子树的深度最大值+1(max(left,right)+1);
      • 当节点root左/右子树的深度差大于2;则返回-1,代表此子树不是平衡树。
    • 终止条件:
      • 当root为空:说明越过叶节点,因此返回高度0;
      • 当左(右)子树深度-1:代表此树的左(右)子树不是平衡树,因此剪枝,直接返回-1;

    isBalanced(root)函数:

    • 返回值:若recur(root)!=-1,则说明此树平衡,返回true;否则返回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 (root == null) return true;
            return recur(root) == -1 ? false : true;
        }
        private int recur(TreeNode node) {
            if (node == null) return 0;
            int left = recur(node.left);
            if (left == -1) return -1;
            int right = recur(node.right);
            if (right == -1) return -1;
            return Math.abs(left - right) < 2 ? Math.max(left,right) + 1 : -1;
        }
    }
    

    复杂度分析:

    • 时间复杂度O(N):N为树的节点数;最差情况下,需要递归遍历树的所有节点。
    • 空间复杂度O(N):最差情况下(树退化为链表时),系统递归需要使用O(N)的栈空间。

    2.2 方法2:先序遍历 + 判断深度 (从顶至底)

    思路是构造一个获取当前子树的深度的函数depth(root),通过比较某子树的左右子树的深度差abs(depth(root.left)-depth(root.right)) <= 1是否成立,来判断某子树是否是二叉平衡树。若所有子树都是平衡,则此树平衡。

    算法流程:
    isBalanced(root)函数:判断树root是否平衡

    • 特例处理:若树根节点root为空,则直接返回true;
    • 返回值:所有子树都需要满足平衡树性质,因此以下三者使用与逻辑&&连接;
      • abs(depth(root.left)-depth(root.right))<=1:判断当前子树是否为平衡树;
      • isBalanced(root.left):先序遍历递归,判断当前子树的左子树是否平衡树;
      • isBalanced(root.right):先序遍历递归,判断当前子树的右子树是否为平衡树;
        wei
        depth(root)函数:计算树root的深度。
    • 终止条件:当root为空,即越过叶子节点,则返回高度0;
    • 返回值:返回左/右子树的深度的最大值+1。
    /**
     * 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 (root == null) return true;
            return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
        private int depth(TreeNode node) {
            if (node == null) return 0;
            return Math.max(depth(node.left),depth(node.right)) + 1;
        }
    }
    

    复杂度分析:
    时间复杂度O(NlogN):最差情况下(为“满二叉树”时),isBalanced(root)遍历树所有节点,判断每个节点的深度depth(root)需要遍历各子树的所有节点。

    • 空间复杂度O(N):最差情况下(树退化为链表时),系统递归需要使用O(N)的栈空间。
    展开全文
  • 数据结构与算法分析笔记与总结(java实现)--二叉树5:平衡二叉树判断练习题

    视频(3)

    子树的概念

    平衡二叉树(AVL树)

    平衡二叉树又叫作AVL树,所谓平衡二叉树是指对于这棵树中的任意根结点,他的左子树和右子树的高度是平衡的,即高度差是0或者1,何为子树的高度?所谓树的高度是指从根结点开始到叶子结点的最长的路径上的结点的数目(与书上有所不同但是以此为准),因此如果一棵二叉树,上面的任何根结点的左右子树的高度差小于1,那么这棵树就是平衡二叉树。直观的来看,如果某个结点开始的左边的最长路径与右边的最长路径的长度差大于1,那么这个结点就是不平衡的,即以该结点为根的树是不平衡的;反之,如果任何一个结点的左右最长路径都小于等于1,那么这棵树就是平衡的二叉树。

     

    Tree5:平衡二叉树判断练习题

    题目:有一棵二叉树,请设计一个算法判断这棵二叉树是否为平衡二叉树。给定二叉树的根结点root,请返回一个bool值,代表这棵树是否为平衡二叉树。

    思路:根据定义,要判断一棵二叉树是否是平衡二叉树需要判断树上的每一个结点的左右子树的高度差是否小于等于1,显然需要遍历左右的根结点。其实对于二叉树而言,遍历时使用的遍历方式无非是先序遍历、中序遍历、后序遍历、按层遍历,选取合适的遍历方式即可。其中,先序遍历实际上是从上到下遍历结点的,由于是先根结点再左右子树,因此大致上是从上到下进行的;中序遍历是先左子树再中间根结点再右子树,因此大致上是从下开始的;后序遍历是先左结点再右结点再根结点,因此大致上是从下向上的,按层遍历特征太明显,从上到下,从左到右。本题中,要判断是否是平衡二叉树,需要对每个结点进行判断,对于每个结点又要得到它的左右子树的高度,如果从上到下遍历会对下部的子树进行多次的重复判断因此应该从下往上遍历子树判断子树是否平衡,即先判断左子树是否平衡,并求出其最大的高度,如果不平衡则整棵树不平衡;同理再求右子树是否平衡以及求出最大的高度,如果不平衡则整棵树不平衡;如果左右子树都平衡,那么比较2左右子树是否平衡即可,显然这是一个递归的过程。由于是先遍历左子树,再遍历右子树再遍历根结点,因此显然应该对后续遍历进行改造。


    二叉树难的地方在于很多时候需要使用递归,而且是需要携带返回值的递归,此时高度抽象,但是不要灰心,需要多理解,多练习,找找感觉。

    很巧妙,很简单:

    其实还是一个递归的过程,构造一个递归函数,函数的功能是给定一个一棵子树的根结点root,返回这棵树的高度:递推关系是:对于任何一个跟结点,它的高度是其左右子树高度+1,即比较得到2个子树的高度,选取较大的高度+1即为当前结点的高度,于是求某个结点的高度转化为求它的子树的高度,这显然是一个递推的过程,递推的边界条件是当一直向下递推时,如果某个结点的子树为null,那么这棵子树的高度为0,同时表示到达叶子结点,递归结束return即可。由于需要判断是否是平衡二叉树,于是在求出左右子树的高度同时稍微改编加一些逻辑即可:

    写一个递归函数,输入一个根结点,判断这个根结点所在的树是否是平衡二叉树,如果是则返回这棵树的高度,如果不是就返回-1;

    ①递归的递推条件:判断一棵二叉树是否平衡并求出高度,可以转化为分别判断左右二叉树是否平衡并求出其高度,如果有某一棵子树不是平衡的就直接return -1,如果2子树都不返回-1,那么判断2子树返回的高度差是否<=1,如果不是则返回-1,如果是就返回2棵子树中高度较大的值作为当前子树的高度。

    ②基准情形:当root为null时,说明是求null结点的高度,显然是0,直接返回0即可。

    基准情形也可以理解为边界条件,因为此时的结果是明显的,不需要递归调用,可以直接返回一个明确的值,或者不返回值而是直接return,例如之前遍历时当stack==null时直接return也可以认为是基准情形。

    关键是根据逻辑要求构造出一个递归函数。

     

    importjava.util.*;

    //判断一棵二叉树是否是平衡二叉树,使用递归,以子树的高度作为返回值

    publicclass CheckBalance {

        public boolean check(TreeNode root) {

            //调用递归方法来判断是否是平衡的

           //如果返回-1表不平衡,如果返回一个具体的值,说明树平衡,返回的是树的高度值

            booleanresult=this.getHeight(root)==-1?false:true;

            return result;

        }

        //这是一个递归的方法,用于返回一棵二叉树的高度,如果平衡返回高度,如果不平衡返回-1

        private int getHeight(TreeNode root){

           //基准情形

            if(root==null) return 0;

            //先求左子树的高度

            intleftHeight=this.getHeight(root.left);

           //判断左子树是否平衡,调用递归方法后总是认为这个方法已经全部执行完毕

            if(leftHeight==-1) return -1;

           //再求右子树的高度

            intrightHeight=this.getHeight(root.right);

           //判断右子树是否平衡

            if(rightHeight==-1) return -1;

           //判断高度差是否过大

            if(Math.abs(leftHeight-rightHeight)>1) return -1;

           //执行到此处说明二叉树平衡,返回此树的高度(子树较大值+1

            returnMath.max(leftHeight,rightHeight)+1;

        }

    }

     

    搜索二叉树

    搜索二叉树又叫作二叉树查找树或者二叉排序树,


    所谓搜索二叉树是指对于任何一个结点,它的左子树的所有结点都比这个根结点要小,它的右子树的所有结点都比这个根结点要大。注意是根结点与左右子树上所有的结点进行比较而不是仅仅与左右孩子结点进行比较,因此根据这个定义,那么当按照中序遍历来遍历一棵搜索二叉树时,必然是单调递增的,即是有序的序列,反之,如果一棵二叉树按照中序遍历得到的序列时有序的,那么这棵二叉树一定是搜索二叉树,因此对于搜索二叉树通常总是进行中序遍历的操作。

    红黑树、平衡搜索二叉树(AVL树)等其实都是搜索二叉树的不同实现,它们都努力使得搜索二叉树的搜索效率更高,调整代价更小。

    题目:判断一棵二叉树是否是搜索二叉树

    思路:根据定义检查在进行中序遍历时结点值是否递增即可,如果一旦出现减小,必然不是搜索二叉树。

    可以使用递归也可以不使用递归,当使用递归时注意,由于每次遍历到的结点需要与上一个结点进行比较,因此要保留上一个结点的值,因此在递归外面要设置一个成员变量temp(不能是局部变量)用来记住上一次遍历到的结点值,如果本次结点>=temp表示符合要求,再将temp替换为当前的值即可。并且,为了使得当遇到<temp的结点时停止,因此要设置一个falg变量作为标记符,每次判断当前值与temp时如果不符合要去就将falg设置为false,然后结束方法。

    packagecom.caicainiao.nowcoder;

    //主函数

    publicclass SearchBinaryTree {

             public static void main(String[] args){

                       TreeNode node1=newTreeNode(1);

                       TreeNode node2=newTreeNode(2);

                       TreeNode node3=newTreeNode(3);

                       TreeNode node4=new TreeNode(4);

                       TreeNode node5=newTreeNode(5);

                       TreeNode node6=newTreeNode(6);

                       TreeNode node7=newTreeNode(7);

                       node4.left=node2;

                       node4.right=node6;

                       node2.left=node1;

                       node2.right=node3;

                       node6.left=node5;

                       node6.right=node7;

                       new SearchBinaryTree().checkIsSearch(node4);

             }

            

             //辅助变量:成员变量,所有递归栈共享

             int temp;

             boolean flag=true;

            

             //判断是否是搜索二叉树,中序遍历

             public void checkIsSearch(TreeNodetreeNode ){

                       temp=Integer.MIN_VALUE;

                       this.inOrderRecru(treeNode);

                       if(flag){

                                System.out.println("是搜索二叉树");

                       }else{

                                System.out.println("不是搜索二叉树");

                       }

             }

            

             //中序遍历,同时判断是否递增

              private void inOrderRecru(TreeNode treeNode){

                        //这是一个递归方法,要有结束的边界条件,当没有子节点时返回

                    if(treeNode==null) return;

                    //①先遍历子树的左子树

                    this.inOrderRecru(treeNode.left);

                    //②与前一个结点值比较

                    if(treeNode.val<temp){

                       flag=false;

                       return;

                    }

                    temp=treeNode.val;

                    //③遍历子树的右子树

                    this.inOrderRecru(treeNode.right);

                }

    }

    满二叉树与完全二叉树

    所谓的满二叉树是指一棵二叉树中除了最后一层的结点没有任何子节点之外,剩下每一层上的结点都有2个子节点,即直观地看,满二叉树没有任何确实的结点。对于满二叉树,它的结点数目与层数存在直接的对应关系,如果层数为L,那么满二叉树的结点数目为N=2^L-1,反之L=log2(N+1)

     

    所谓完全二叉树是指除了最后一层之外,其他每一层的结点数目都是满的,如果最后一层也满了就是满二叉树,如果最后一层不满那么结点全部集中在左侧。满二叉树是一棵特殊的完全二叉树,对于完全二叉树这种特殊的结构,它可以使用数组来表示各个结点,此时每个结点与它的子节点的位置下标之间存在直接的对应关系,即从数组中i=1开始存放元素,于是对于某个结点i,它的左孩子下标是2*i,它的右孩子结点时2*i+1,它的父节点下标是i/2。堆(优先队列)就是一种完全二叉树结构。


    展开全文
  • 二叉树练习题及答案解析

    千次阅读 2021-11-01 15:41:39
    二叉树练习一、选择1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )2.在具有 2n 个结点的完全二叉树中,叶子结点个数为( )3.一棵完全二叉树的节点数位为531个,那么...
  • 文章目录单选选择题解编程7-3 插入排序还是堆排序 (25分) 不会输入格式:输出格式:输入样例 1:输出样例 1:输入样例 2...在下列所示的平衡二叉树中,插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中,关
  • 1. 二叉树的前序遍历。 解题思路: 使用递归的方法,先访问根节点、再访问左子树、再访问右子树。 代码如下: class Node{ String val; Node left; Node right; public Node(String val){ this.val=val...
  • 平衡二叉树、二叉树的经典 1 平衡二叉树 题目 输入一棵二叉树,判断该二叉树是否是平衡二叉树平衡二叉树:每个子树的深度之差不超过1 思路 后续遍历二叉树,在遍历二叉树每个节点前都会遍历其左右子树 ...
  • 中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:true 示例 2: 输入:root = [1,2,2,3,3,null,null,4,4...
  • 数据结构之二叉树练习题
  • 中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 代码: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; ...
  • 二叉树经典练习题合集(Java实现)

    千次阅读 2022-03-22 18:50:53
    二叉树的问题大多是以递归思想求解,也可以利用...平衡二叉树 对称二叉树 迭代实现(利用队列实现) 递归实现 二叉树的层次遍历 树的重要概念总结 ①结点的度:一个结点含有子树的个数称为该结点的度; ②树...
  • 平衡二叉树 KY11 二叉树遍历如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时,才返回 ;否则返回 。示例: 解答:思路:判断一整个树的值是否都相同,可以拆分成判断 根...
  • 【二叉树】平衡二叉树判断练习题

    千次阅读 2018-09-06 19:23:41
    **有一棵二叉树,请设计一个算法判断这棵二叉树是否为平衡二叉树。 给定二叉树的根结点root,请返回一个bool值,代表这棵树是否为平衡二叉树。** import java.util.*; /* public class TreeNode { int ...
  • 第 6 章 树和二叉树 1选择 TOC \o "1-5" \h \z 1把一棵树转换为二叉树后这棵二叉树的形态是 A.唯一的 E.有多种 C.有多种但根结点都没有左孩子 D.有多种但根结点都没有右孩子 2 由 3 个结点可以构造出多少种不同的...
  • 二叉树练习题二叉树的高度-只能汇总思想 int getHeight(Node root) { if(root==null) { return 0; } int left=getHeight(root.left); int right=getHeight(root.right); return Math.max(left,right...
  • 中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] ...
  • 源:https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/submissions/ 初始代码: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNod...
  • title: 每日一练(28):平衡二叉树 categories:[剑指offer] tags:[每日一练] date: 2022/03/01 每日一练(28):平衡二叉树 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树...
  • 平衡二叉树

    2019-11-07 13:00:27
    平衡二叉树(Balanced Binary Tree)具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 思路: 递归判断左右子树的高度,比较高度差。 import java.util...
  • 考研之数据结构016_平衡二叉树AVL一、定义二、插入操作三、插入后调整“不平衡”问题1.LL左孩子左子树平衡旋转(右单旋转)1.LL代码:2.RR右孩子右子树平衡旋转(左单旋转)1.RR代码:3.LR左孩子右子树平衡旋转( ...
  • 平衡二叉树之平衡调整图解

    万次阅读 多人点赞 2019-02-22 22:46:47
    先看一个平衡二叉树创建的例子。假设现在表中关键字序列为(13,24,37),具体的平衡二叉树创建过程如下图所示: 我们可以发现结点37的插入导致二叉树的根结点13的平衡因子变为-2,此时二叉树没有达到平衡状态。...
  • 二叉树练习题

    2022-06-27 17:38:24
    二叉树的类型总结:求树中节点个数、叶子节点个数、第k层节点个数、树的高度,检测值为value的元素是否存在,二叉树的前中后序遍历的相关问题(递归和非递归两种方法),平衡二叉树、对称二叉树、层序遍历、二叉...
  • 题目介绍: 将给定的一系列数字插入初始为空的AVL树,请你输出最后生成的AVL树的根结点的值。 输入格式: 输入的第一行给出一个正整数N(≤20),随后一行给出N个不同的整数,其间以空格分隔。 输出格式: ...
  • 二叉树相关OJ题目——二叉树的高度,平衡二叉树的判断
  • 平衡二叉树的最大深度和最少节点数

    千次阅读 多人点赞 2021-06-11 12:01:09
    写在前边的话:你的支持是我写作的动力,有帮助到你的话麻烦点赞加收藏呦。... 【2012统考真题】若平衡二叉树的高度为 6,且所有非叶子结点的平衡因子均为1,则该平衡二叉树的结点总数为()。 A.12 B.20 C.32 D.33

空空如也

空空如也

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

平衡二叉树习题