-
2020-04-05 17:57:36
只标注困难和简单的题目,中等题不标注
树的遍历
中,后,前序遍历题,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)√
更多相关内容 -
平衡二叉树
2021-01-17 15:11:38平衡二叉树思路一:求每个节点的左右子树深度,根据深度差判断,直到叶子节点结束,效率不够高,每个节点都要用两次计算深度的递归函数思路二:从叶子节点开始,计算深度差,一旦有深度差大于1的,就直接返回0,也...AcWing 72. 平衡二叉树
思路一:求每个节点的左右子树深度,根据深度差判断,直到叶子节点结束,效率不够高,每个节点都要用两次计算深度的递归函数
思路二:从叶子节点开始,计算深度差,一旦有深度差大于1的,就直接返回0,也不用管上面的深度是不是正确了,毕竟我们只需要true和false两种状态,省略了很多次深度的计算
思路二的代码
class Solution {
boolean balanced=true;
public boolean isBalanced(TreeNode root) {
getDepth(root);
return balanced;
}
int getDepth(TreeNode root){
if(root==null) return 0;
int left=getDepth(root.left);
if(!balanced) return 0;
int right=getDepth(root.right);
if(!balanced) return 0;
if(Math.abs(left-right)>1) {
balanced=false;
return 0;
}
return 1+Math.max(left,right);
}
}
发布于 2020-02-16
AcWing 72. Go 题解 平衡二叉树
Talke is cheap.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
return isBalan(root) != -1
}
func isBalan(root *TreeNode) int {
if root == nil {
return 0
}
left := isBalan(root.Left)
right := isBalan(root.Right)
if left == -1 || right == -1 || left - right > 1 || left - right < -1 {
return -1
}
if left > right {
return left + 1
}
return right + 1
}
发布于 2020-02-16
AcWing 72. 平衡二叉树
C++几行直接解决
算法
直接用高度h,平衡二叉树递归满足1、左右子树是平衡的
2、左子树-右子树高度的绝对值<2
时间复杂度
o(n)
/**
* 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:
bool isBalanced(TreeNode* root) {
if(!root) return true;
return isBalanced(root->left)&&isBalanced(root->right)&&abs(h(root->left)-h(root->right))<2;
}
int h(TreeNode *bt)
{
if(!bt)return 0;
return max(h(bt->left),h(bt->right))+1;
}
};
发布于 2020-02-16
AcWing 72. 平衡二叉树
题目描述
blablabla
算法1
(暴力枚举) $O(n)$
将求深度的代码稍作修改,不重复求深度。
时间复杂度分析:因为只遍历结点一次,所以最坏情形为O(n)
C++ 代码
class Solution {
public:
bool isBalanced(TreeNode* root) {
/*
unit test
root is nil
root not nil, left is nil, right is nil
root not nil, left not nil, right nil.
*/
int height=dfs(root);
if(height>=0) return true;
else return false;
}
// 当非平衡时,return -1; 平衡时,return high;
// 首先判断左子树平衡与否,再判断右子树平衡与否,在判断整棵树平衡与否;
int dfs(TreeNode *root){
if(!root) return 0;
int left=dfs(root->left);
if(left<0) return -1;
int right=dfs(root->right);
if(right<0) return -1;
if(abs(left-right)>1) return -1;
return max(left,right)+1;
}
};
发布于 2020-02-16
AcWing 72. 平衡二叉树
题目描述
输入二叉树的根节点,判断该树是不是平衡二叉树
样例
输入:二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示,
5
/ \
7 11
/ \
12 9
输出:true
算法
递归
可以结合二叉树深度的方法,递归判断每一个结点的左右子树是否都满足深度相差小于1的条件
C++ 代码
class Solution {
public:
#计算树的深度
int treeDepth(TreeNode* root){
if(!root) return 0;
return max(treeDepth(root->left),treeDepth(root->right))+1;
}
bool isBalanced(TreeNode* root) {
if(!root) return true;
int left = treeDepth(root->left);
int right = treeDepth(root->right);
#判断左右子树是否满足条件,然后如果满足条件,判断子树的子树是否满足条件
if(abs(left-right)<=1) return isBalanced(root->left)&&isBalanced(root->right);
#如果不满足条件直接返回false
else return false;
}
};
发布于 2020-02-16
AcWing 72. 平衡二叉树--Java代码
算法1
(递归)
在上一题的基础上,得出左右子树的深度,然后求差,如果大于1,则返回false;
然后递归每个节点,这个算法的弊端是,每个节点递归两次
Java 代码
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
int left = treeDepth(root.left);
int right = treeDepth(root.right);
int diff = left-right;
if(Math.abs(diff)>1)
return false;
return isBalanced(root.left)&&isBalanced(root.right);
}
public int treeDepth(TreeNode root) {
if(root==null){
return 0;
}
int left = treeDepth(root.left);
int right = treeDepth(root.right);
return left>right?left+1:right+1;
}
}
算法2
(后序遍历) $O(n)$
后续遍历,得到的左右子树的高度差立即进行判断即可
Java 代码
class Solution {
private boolean isBalanced=true;
public boolean isBalanced(TreeNode root) {
getDepth(root);
return isBalanced;
}
public int getDepth(TreeNode root){
if(root==null)
return 0;
int left=getDepth(root.left);
int right=getDepth(root.right);
if(Math.abs(left-right)>1){
isBalanced=false;
}
return right>left ?right+1:left+1;
}
}
发布于 2020-02-16
AcWing 72. 平衡二叉树
题目描述
本题的思路就是对于每一个节点,依次递归求出每个节点的左子树高度和右子树高度,如果左右子树的高度之差大于1.就说明该二叉树非平衡。对于每一次返回值此处需要强调下,是返回该节点左右子树中的最大值,第二点需要强调的是对于root节点,只用判断其左右子树的高度差是否大于1即可,不需要加上root的高度。
算法1
(dfs) $O(n)$
C++ 代码
/**
* 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:
bool ans = true;
bool isBalanced(TreeNode* root) {
if(!root) return true;
int leftDepth = dfs(root->left);
int rightDepth = dfs(root->right);
if (abs(leftDepth - rightDepth) <= 1 && ans) return true;
return false;
}
int dfs(TreeNode* root)
{
if(!root) return 0;
if(ans == false) return 0;
int leftDepth = dfs(root->left) + 1;
int rightDepth = dfs(root->right) + 1;
if(abs(leftDepth - rightDepth) <= 1) ans = true;
else ans = false;
return max(leftDepth, rightDepth);
}
};
发布于 2020-02-16
AcWing 72. 平衡二叉树
题目描述
blablabla
样例
blablabla
算法1
blablabla
时间复杂度分析:blablabla
C++ 代码
class Solution {
public boolean isBalanced(TreeNode root) {
return isBalanced1(root).flag;
}
static class Res{
int h;
boolean flag;
public Res(int h, boolean flag) {
this.h = h;
this.flag = flag;
}
}
public Res isBalanced1(TreeNode root) {
if (root==null){
return new Res(0,true);
}
Res a=isBalanced1(root.left);
Res b=isBalanced1(root.right);
if (a.flag&&b.flag)
return new Res(Math.max(a.h,b.h)+1,Math.abs(a.h-b.h)<=1);
return new Res(-1,false);
}
}
发布于 2020-02-16
AcWing 72. python看我
题目描述
blablabla
样例
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
ans = True
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
self.helper(root)
return self.ans
def helper(self, root):
if not root:
return 0
left = self.helper(root.left)
right = self.helper(root.right)
if abs(right - left) > 1:
self.ans = False
return right + 1 if right > left else left + 1
发布于 2020-02-16
-
平衡二叉树习题
2020-05-18 09:56:401、给定一个二叉树,判断它是否是高度平衡的二叉树。 示例 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); } };
-
110题:平衡二叉树
2020-08-04 16:42:35本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 https://leetcode-cn.com/problems/balanced-binary-tree/ 深度值是一个很好地反映子树是否失衡的量。设当深度值...给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
https://leetcode-cn.com/problems/balanced-binary-tree/深度值是一个很好地反映子树是否失衡的量。设当深度值为-1时,二叉树失衡。
getDepth递归函数 :从叶子节点开始计算深度。计算非叶子节点的左右子树深度,如果相差值大于1,则返回-1表示失衡。
该函数的具体逻辑为:- 首先节点如果为空,直接返回深度。(可以理解为空子树深度为0)
- 如果是叶子节点,返回深度+1,即1。(由于“归”的起点是叶子,最外层调用传参的深度是0,所以叶子节点作为参数时的返回值总是1)
- 不是叶子节点,则递归调用getDepth函数计算左右子树的深度。
- 如果左右子树中途出现失衡(得到深度值为-1),或者左右子树深度差大于1(说明在该节点失衡),则直接返回-1。
- 如果上述情况都没出现,正常返回左右子树深度中较大的一个值+1,作为调用者的参考。
class Solution { public int max(int a,int b){ return a > b ? a : b; } public int abs(int a) { return a > 0 ? a : -a; } public int getDepth(TreeNode p, int dep){ if (p == null) return dep; if (p.left == null && p.right == null) return dep + 1; int left = getDepth(p.left, 0); int right = getDepth(p.right, 0); if (left == -1 || right == -1 || abs(left - right) > 1) return -1; return max(left, right) + 1; } public boolean isBalanced(TreeNode root) { if (root == null) return true; if (root.left == null && root.right == null) return true; if ( getDepth(root,0) == -1) return false; return true; } }
注意节点数为0或1时也是平衡二叉树。
-
练习题目-平衡二叉树
2016-10-13 12:07:09平衡二叉树(Balanced Binary Tree)具有以下性质的一种树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树 讲完了slowlight就给NotDeep出了一道练习题:一棵... -
【每日一题】平衡二叉树
2020-10-25 20:44:37题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树。...由平衡二叉树的定义(一棵二叉树是平衡二叉树,当且仅当其所有子树也都是平衡二叉树),因此可以采用递归的方法进行判断。 采用自顶向下的递归方法,先判 -
面试题:平衡二叉树
2021-01-17 15:11:38题目描述输入一棵二叉树,判断该二叉树是否是平衡二叉树。知识点平衡二叉树Qiang的思路平衡二叉树是指一个二叉树的左子树深度相差不超过1,可以相等或相差为1。为了判断一个二叉树是不是平衡二叉树,我们只需要计算... -
LintCode:平衡二叉树
2016-04-26 22:42:48LintCode:平衡二叉树""" Definition of TreeNode: class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, None """ class Solution: """ @param root: The -
数据结构与算法分析笔记与总结(java实现)--二叉树5:平衡二叉树判断练习题
2017-02-15 17:30:29数据结构与算法分析笔记与总结(java实现)--二叉树5:平衡二叉树判断练习题 -
经典算法题——平衡二叉树
2021-04-14 17:32:51平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 - 示例: 输入: {1,2,3,4,5,6,7} 输出: true - 思路分析: ... -
1077: 平衡二叉树的判定
2021-05-18 11:53:02编写程序判断给定的二叉树是否是平衡二叉树。 输入 二叉树的先序序列。 输出 如果是平衡二叉树,输出yes!,否者输出no! 样例输入 AB##C## 样例输出 yes! 平衡二叉树:若一颗二叉树中每个结点的左、右子树的... -
《剑指Offer》刷题笔记——面试题55-II. 平衡二叉树
2020-12-22 07:42:21一、题目描述: 二、解题分析: 1、剑指解析 I、自顶向下 II、自底向上 2、代码实现 I、自顶向下 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left... -
判断平衡二叉树
2020-08-13 18:29:51判断平衡二叉树题目详情示例题解方法一:先序遍历(自顶向下) 题目详情 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度... -
平衡二叉树是什么?平衡二叉树的解题思路。
2021-03-04 10:20:59平衡二叉树题目描述:知识点解题思路代码块 该题目出自:剑指 Offer 55 - II. 平衡二叉树 题目描述: 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。 示例 : 给定二叉树 [3,9,20,null,null,15,7] 3 / \ ... -
判断一棵二叉树是否为平衡二叉树
2022-03-07 19:38:59基于递归判断一棵二叉树是否为平衡二叉树题目解决思路代码说明 题目 (1)给定一个二叉树,判断它是否是高度平衡的二叉树。 (2)本题中,一棵高度平衡二叉树的定义为:一个二叉树每个节点 的左右两个子树的高度差的... -
二十六、平衡二叉树
2020-11-14 22:06:42文章目录二十六、平衡二叉树题目描述解题思路上机代码 题目描述 程序输入一个字符串(只包含小写字母),请按照字符的输入顺序建立平衡二叉排序树,并分别输出二叉树的先序序列、中序序列和后序序列,最后输出该... -
《剑指offer》第五十五题(平衡二叉树)
2021-01-17 15:11:35//面试题55(二):平衡二叉树//题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中//任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。#include#include"BinaryTree.h"//=====... -
Java 求解平衡二叉树
2021-11-22 15:45:55本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 二、题目分析 该题和求解二叉树的最大深度有很大区别: 二叉树节点的深度:指从根节点到该节点的最长的简单... -
代码实现平衡二叉树
2020-12-16 07:13:28实现二叉树对于我们已经算是轻车熟路了。先来定义树的结点:class AVLNode {public int data;public int depth;public int balance;public AVLNode parent;public AVLNode left;public AVLNode right;public AVLNode... -
算法题目:平衡二叉树
2020-08-17 11:09:03思路:本来,我看到这道题目的第一想法的遍历二叉树,然后计算每个节点的高度。我当时的想法就很简单,前序遍历并且计算,但是仔细一想这样会产生大量的重复计算,感觉题目这样子解不太好。当时看了一下题目的评论,... -
面试题39-题目2:平衡二叉树
2017-02-19 22:36:15面试题39-题目2:平衡二叉树 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 代码: package offer; /** * 面试题39: * 题目2:平衡二叉树 * 输入一棵二叉树,判断该二叉树是否是... -
二叉树题目----5 平衡二叉树 AND 根据二叉树创建字符串
2019-10-08 18:55:00平衡二叉树 /** * 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... -
题目:平衡二叉树
2015-09-29 00:01:51给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。 您在真实的面试中是否遇到过这个题? Yes 样例 给出... -
关于树的判定(满二叉树、完全二叉树、平衡二叉树、相似二叉树、等价二叉树)
2021-07-20 11:39:11文章目录满二叉树完全二叉树相似二叉树等价二叉树 满二叉树 题目描述: 设二叉树采用二叉链表存储,设计一个算法,判断二叉树是否是满二叉树。 算法思想: 满二叉树即深度为h,结点个数为2h-1的二叉树。 实现... -
平衡二叉树的旋转以及简便方法
2021-04-06 22:24:33刚开始听这个平衡二叉树的旋转,一听就蒙了,后来看了很多视频,有很多的说法。下面来介绍平衡二叉树 平衡二叉树:就是每个节点的平衡因子(Balance Factor)(以下简称BF)的绝对值小于等于1,即为0或1。 而BF就是每... -
二叉树:判断一个树是否是平衡二叉树
2020-10-15 17:51:19题目:给定一个二叉树,判断其是否是平衡二叉树。 方法一: bool isBalancedTree(TreeNode* root) { if(root == NULL) return true; int Lh = getHeight(root->left); int Rh = getHeight(root->right);... -
判断一棵树是否是平衡二叉树(leetcode题目 110)
2020-02-16 12:59:27平衡二叉树就是对每一个节点而言,高度差在1以内(包括1)。所以我们只需要求得每棵子树高度,然后判断是否合理即可。 public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode... -
平衡二叉树的判断
2020-10-24 22:59:16输入一棵二叉树,判断该二叉树是否是平衡二叉树。 在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树 思路: 首先得明白平衡二叉树的概念:在二叉树的基础上,任意结点的左右子树的高度相差不超过1 ...