精华内容
下载资源
问答
  • 只标注困难和简单的题目,中等题不标注 树的遍历 中,后,前序遍历题,n叉树,二叉树的遍历 层次遍历(简单) (主要复习一下非递归的解法) 94 中序遍历√ 144 前序遍历√ 145 后序遍历√ 589 n叉树前序遍历√ 590 n...

    只标注困难和简单的题目,中等题不标注

    树的遍历

    中,后,前序遍历题,n叉树,二叉树的遍历 层次遍历(简单) (主要复习一下非递归的解法)

    • 94 中序遍历√
    • 144 前序遍历√
    • 145 后序遍历√
    • 589 n叉树前序遍历√
    • 590 n叉树后序遍历√
    • 429 n叉树层序遍历√
    • 102 二叉树的层次遍历√
    • [236. 二叉树的最近公共祖先
    • [257. 二叉树的所有路径 √(递归、栈均可)

    二叉搜索树

    • [98. 验证二叉搜索树
    • [230. 二叉搜索树中第K小的元素
    • [LeetCode] 272. Closest Binary Search Tree Value II 最近的二分搜索树的值之二
    • [LeetCode] 285. Inorder Successor in BST 二叉搜索树中的中序后继节点
    • [LeetCode] 285. Inorder Successor in BST 二叉搜索树中的中序后继节点
    • [783. 二叉搜索树结点最小距离
    • [173 二叉搜索树迭代器 √
    • [LeetCode] 251. Flatten 2D Vector 压平二维向量
    • [LeetCode] 281. Zigzag Iterator 之字形迭代器
    • [LeetCode] 285. Inorder Successor in BST 二叉搜索树中的中序后继节点
    • [501. 二叉搜索树中的众数(Morris)√
    • [98 验证二叉搜索树 (中序遍历是否符合大小规则)√
    • [99. 恢复二叉搜索树(Morris)√(困难)
    • [671. 二叉树中第二小的节点(简单)
    • [1305. 两棵二叉搜索树中的所有元素
    • 面试题34. 二叉树中和为某一值的路径
    • [leetcode] 325. Maximum Size Subarray Sum Equals k

    学习到的新知识

    Morris中序遍历

    Morris中序遍历
    首先明确:在二叉搜索树中,如果一个结点有前驱结点,那么前驱结点的右指针只有两种情况
    是空的
    是这个结点本身(即前驱是它的父结点)
    所以我们可以把前驱结点的右指针这一特性利用起来,从而降低空间复杂度

    Morris遍历算法的步骤如下:

    检查当前结点的左孩子:

    如果当前结点的左孩子为空,说明要不没有前驱,要不前驱是它的父结点,所以进行检查,然后进入右孩子。
    如果当前结点的左孩子不为空,说明左子树里肯定有它的前驱,那就找到这个前驱
    如果前驱结点的右孩子是空,说明还没检查过左子树,那么把前驱结点的右孩子指向当前结点,然后进入当前结点的左孩子。
    如果当前结点的前驱结点其右孩子指向了它本身,说明左子树已被检查过,就直接进行检查,然后把前驱结点的右孩子设置为空,恢复原树,再进入右孩子。

    在遍历过程中,每个节点最多会被访问两次,一次是从父节点到当前节点,第二次是从前缀节点的右孩子指针返回当前节点,所以Morris遍历算法的复杂度是O(n)。在遍历过程中,没有申请新内存,因此算法的空间复杂度是O(1).

    平衡二叉树

    DFS 深度优先搜索

    • [46. 全排列(DFS) √
    • [47. 全排列 II(不必求出所有的全排列 DFS+ 剪枝) √
    • [113. 路径总和 II (DFS + 状态重置)√
    • [112. 路径总和 (DFS)√
    • [437. 路径总和 III(两次递归 或者 前缀和)√
    • 路径和 IV
    • [491. 递增子序列(深度优先搜索+剪枝判重 unordered_map) √
    • [31. 下一个排列
    • [60. 第k个排列
    • [77. 组合
    • [529. 扫雷游戏(DFS BFS均可)
    • [756. 金字塔转换矩阵
    • [LeetCode] 267. Palindrome Permutation II 回文全排列之二
    • [996. 正方形数组的数目(困难)

    C++中find()函数用法

    //find() 返回值是目标元素的下标,找不到时返回值为迭代器结尾
    find(track.begin(), track.end(), nums[i]) == track.end()
    

    C++ std::unordered_map 用法

    在容器中搜索键值等于 k 的元素,如果找到,则返回一个指向该元素的迭代器,否则返回一个指向unordered_map :: end的迭代器。

    动态规划

    • [300. 最长上升子序列 √(动态规划 N^2 √ 优化:NlogN)
    • [646. 最长数对链
    • 递增的三元子序列
    • 俄罗斯套娃信封问题 (困难 )
    • 最长数对链
    • 最长递增子序列的个数
    • 两个字符串的最小ASCII删除和

    贪心算法

    • [646. 最长数对链
    • [435. 无重复区间(medium)
    • [991. 坏了的计算器
    • [300. 最长上升子序列

    窗口

    • [1297. 子串的最大出现次数

    其他:

    • [284. 顶端迭代器 √
    • [640. 求解方程(分别处理左右表达式获取常数与变量系数)
    • [728. 自除数
    • 面试题 16.07. 最大数值(位运算,(sum+abs)/2)√
    展开全文
  • 平衡二叉树题目描述:知识点解题思路代码块 该题目出自:剑指 Offer 55 - II. 平衡二叉树 题目描述: 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。 示例 : 给定二叉树 [3,9,20,null,null,15,7] 3 / \ ...

    该题目出自:剑指 Offer 55 - II. 平衡二叉树

    题目描述:

    输入一棵二叉树的根节点,判断该树是不是平衡二叉树。

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

    知识点

    1.什么是平衡二叉树?
       如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

    2.怎么计算一棵树的深度?
       【运用递归方法的思想】
       特殊情况:如果节点为空时,则深度为0;
       树的深度的求解方法:max(左子树深度,右子树深度)+1
    代码实现:

    private int depth(TreeNode root){
    	if(root==null) return 0;
        return Math.max(depth(root.left),depth(root.right)) +1;
    }
    

    解题思路

    明确了以上两个知识点,应用递归法解决【强烈推荐递归法的思路,可以大大减少代码量】
    解决这道题的思路如下:
    0.特殊情况:如果节点为空时,则返回true;
    1.对根节点进行判断,分别求出它的左右子树的深度,且二者相差不超过1,这为判断该树是否平衡的条件一;
    2.根节点的左右子树也得为平衡树,即它们分别的左右子树深度差不超过1,若其中一个不为平衡树,则整棵树都不是平衡的,明显得用到递归的方法去遍历判断。

    代码块

    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 root){
            //计算树的深度的方法
            if(root==null){return 0;}//特殊情况
            return Math.max(depth(root.left),depth(root.right)) +1;}
    }
    
    展开全文
  • 平衡二叉树

    2020-01-03 14:40:59
    题目要求判断一棵树是否是平衡二叉树,首先我们需要了解平衡二叉树的数据结构如下,它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。所以我们可以使用递归方式去得到...

    平衡二叉树

    题目描述

    输入一棵二叉树,判断该二叉树是否是平衡二叉树。

    题目解析

    题目要求判断一棵树是否是平衡二叉树,首先我们需要了解平衡二叉树的数据结构如下,它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。所以我们可以使用递归方式去得到左右子树的高度如下

    代码

    public class Solution {
        public boolean IsBalanced_Solution(TreeNode root) {
            //它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树
            if(root == null){
                return true;
            }
            return Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1 && IsBalanced_Solution(root.left) && 
                IsBalanced_Solution(root.right);
        }
        //得到树的深度
        private int getDepth(TreeNode root){
            if(root == null){
                return 0;
            }
            return 1 + Math.max(getDepth(root.left),getDepth(root.right));
        }
    }
    
    展开全文
  • 平衡二叉树 /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int MAX(int a,int b) { return a > b...

    平衡二叉树

    在这里插入图片描述

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    
    int MAX(int a,int b)
    {
        return a > b ? a : b;
    }
    
    //求高度
    int getHeight(struct TreeNode *root){
        if(root == NULL){
            return 0;
        }
    
        int left =getHeight(root->left);
        int right =getHeight(root->right);
    
        return MAX(left,right)+1;
    }
    bool isBalanced(struct TreeNode* root){
        if(root == NULL){
            return true;
        }
        //左子树是不是平衡二叉树
            bool is_left_balance =isBalanced(root->left);
            if(is_left_balance == false){
                return false;
            }
    	//右子树是不是平衡二叉树
            bool is_right_balance =isBalanced(root->right);
            if(is_right_balance == false){
                return false;
            }
            int left_height = getHeight(root->left);
            int right_height = getHeight(root->right);
            int diff =left_height-right_height;
    	//左右子树高度差要小于1	
            if(diff >= -1 && diff <=1){
                return true;
            }else{
                return false;
            }
    }
    

    根据二叉树创建字符串

    在这里插入图片描述

    class Solution {
    public:
        string tree2str(TreeNode* t) {
            if(t==nullptr)
                return "";
            stringstream ss;
            function<void(TreeNode*)> helper = [&ss, &helper](TreeNode* t){
                ss<<t->val;
                if(t->left==nullptr){
                    if(t->right!=nullptr){
                        ss<<"()(";
                        helper(t->right);
                        ss<<')';
                    }
                }
                else if(t->right==nullptr){
                    ss<<'(';
                    helper(t->left);
                    ss<<')';
                }
                else{
                    ss<<'(';
                    helper(t->left);
                    ss<<")(";
                    helper(t->right);
                    ss<<')';
                }
            };
            helper(t);
            string s;
            ss>>s;
            return s;
        }
    };
    
    展开全文
  • 面试题39-题目2:平衡二叉树 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 代码: package offer; /** * 面试题39: * 题目2:平衡二叉树 * 输入一棵二叉树,判断该二叉树是否是...
  • 力扣关于平衡二叉树题目还是有一些的,并且都非常经典,推荐大家练习。今天给大家精选了 4 道题,如果你彻底搞明白了这几道题,碰到其他的平衡二叉树题目应该不至于没有思路。当你领会了我的思路之后, 建议再找...
  • 力扣关于平衡二叉树题目还是有一些的,并且都非常经典,推荐大家练习。今天给大家精选了 4 道题,如果你彻底搞明白了这几道题,碰到其他的平衡二叉树题目应该不至于没有思路。当你领会了我的思路之后, 建议再找...
  • Leetcode 平衡二叉树

    2021-03-16 22:36:40
    平衡二叉树 题目描述: 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为:      一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 ...
  • 110. 平衡二叉树

    2020-06-17 09:15:29
    首先判断左子树是不是平衡二叉树,然后判断右子树是不是平衡二叉树,最后确定自己是不是平衡二叉树。 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * ...
  • 判断二叉树是否为平衡二叉树 题目 给定一棵树,判断是否为平衡二叉树 思路1 逐层根据高度判断是否平衡 def is_balance1(self): def height(node): if node is None: return 0 l = height(node.left) ...
  • 判断平衡二叉树

    2020-08-13 18:29:51
    判断平衡二叉树题目详情示例题解方法一:先序遍历(自顶向下) 题目详情        输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度...
  • 110平衡二叉树

    2019-11-07 20:35:09
    平衡二叉树 题目描述: 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null...

空空如也

空空如也

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

平衡二叉树题目