二叉树常见类型 1、满二叉树 一棵二叉树的结点要么是叶子结点，要么它有两个子结点（如果一个二叉树的层数为K，且结点总数是(2^k) -1，则它就是满二叉树。） 层数与此层节点数的对应关系：第K层，节点数为2^(K)。K从0开始。 计算公式 等比数列求和公式 最终得出 2、完全二叉树 若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。 3、平衡...
本系列旨在对比不同LeetCode的解题方法效率，占用空间等方面的区别，希望帮助大家能够精进代码水平，用更好的思维与方法去解题。其中的部分解题可能涉及代码的奇技淫巧，我回尽量给大家解释，我也会标注正常的思路至少应该达到何种水准，如果有更好的方法也请大家多多指教！ 本系列的资源消耗数据由LeetCode给出，但是LeetCode的评价会有20ms左右的波动，这里列出的只是显示的最优成绩，但是直接复制这里的结果不一定能跑出同样的成...
一个有效的二叉搜索树（Validate Binary Search Tree)的定义是每一个节点一定大于左边的所有节点，并且小于等于右边的节点。 一个模拟BST的网站： https://www.cs.usfca.edu/~galles/visualization/BST.html Solution 基本的思路是基于有效BST的基本性质，以当前节点作为出发节点，左右进行比较。比较的退出条件是当前的子tree为空，此时认为当前比较的子tree是有效的。 如果整棵树是一个有效的BST那么必须满足： 向左走，数字会越...
问题 力扣 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。 更正式地说，root.val = min(root.left.val, root.right.val) 总成立。 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。 示例 1：输入：root = [2,2,5,null,null,5,7] 输出：5 解释：最小的值是 2 ，第...
第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。 第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。 第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，...
平衡二叉树模板 #include <bits/stdc++.h> using namespace std; struct node {int data;node *l, *r; }; node *ll(node *p) //右旋 {node *q = p->l;p->l = q->r;q->r = p;p = q;return p; } node *rr(node *p) //左旋 {node *q = p->r;p->r = q->l;q->l = p;p = q;return p; } node *lr(node *p) //先左旋再右旋 {p->l = rr(p->l);return ll(p); } node *rl(node *p) //先右旋再左旋 {p->r = ll(p->r);return rr(p); } int dep(n...
Java数据结构和算法（十）——二叉树 接下来我们将会介绍另外一种数据结构——树。二叉树是树这种数据结构的一员，后面我们还会介绍红黑树，2-3-4树等数据结构。那么为什么要使用树？它有什么优点？前面我们介绍数组的数据结构，我们知道对于有序数组，查找很快，并介绍可以通过二分法查找，但是想要在有序数组中插入一个数据项，就必须先找到插入数据项的位置，然后将所有插入位置后面的数据项全部向后移动一位，来给新数据腾出空...
二叉树算法实现 一：二叉链表的建立和遍历 例，建立如图所示二叉链表：# 定义结点类 class BNode:def __init__(self,data=None,lchild=None,rchild=None):self.data = dataself.lchild = lchildself.rchild = rchild# 先序遍历函数 def preorder(T):if T == None:return print(T.data, end="")preorder(T.lchild)preorder(T.rchild)# 中序遍历 def inorder(T):if T == None:returninorder(T.lchild)print(T.data, end="")inorder(T...
题目：原题链接（中等） 标签：并查集、图 解法时间复杂度空间复杂度执行用时Ans 1 (Python)O(N)O(N)O(N)O(N)O(N)O(N)156ms (11.67%)Ans 2 (Python)Ans 3 (Python) 解法一： class DSU1:def __init__(self, n: int):self._n = nself._array = [i for i in range(n)]self._size = [1] * ndef find(self, i: int):if self._array[i] != i:self._array[i] = self.find(self._array[i])return self._array[i]def union(self, i: int, j...
翻转二叉树 题目描述答案步骤详解题目描述答案 步骤详解 分为两个步骤 1）利用二叉树的先序遍历 2）每次遍历都调整左右孩子的位置 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object):def reverse(self,root):TreeNode=root.leftroot.left=root...
描述 给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。 二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。 返回二叉树的 垂序遍历 序...
请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution:def isSymmetrical(self, pRoot):# write code heredef isMirror(left, right):if left == None and right == None:return Trueelif le...
查找与排序（一） 查找与排序（二） 二叉树的遍历 import java.util.Scanner;public class LianXi {//前序遍历public static void preOrder(int []arr, int i){if(i >= arr.length)return;System.out.print(arr[i] + " "); //输出根节点preOrder(arr, 2 * i + 1); //递归输出左子树preOrder(arr, 2 * i + 2); //递归输出右子树}//中序遍历public static void inOrder(int []arr, int i){if(i >= arr.length)return;inOr...
微信搜索：码农StayUp 主页地址：https://gozhuyinglong.github.io 源码分享：https://github.com/gozhuyinglong/blog-demos1. 二叉树（Binary Tree） 二叉树是一棵特殊的树，其结构简单但很重要。二叉树的特点是每个节点最多有两棵子树，并且有左右之分。满二叉树 如果一棵二叉树的所有叶子节点都在最后一层，称为满二叉树。满二叉树的结点总数 = $2^n-1$ （n为层数）。如下图二叉是的层数为3，其结点总数为$2^3-1=7$完全二叉树 一...
微信搜索：码农StayUp 主页地址：https://gozhuyinglong.github.io 源码分享：https://github.com/gozhuyinglong/blog-demos1. AVL树 AVL（Adelson-Velskii 和 Landis）树是带有平衡条件的二叉查找树，又叫做平衡二叉树。在AVL树中任何节点的两个子树高度差最多为1，所以它又被称为高度平衡树。 如下图中可以清晰的看出，左边的树其根节点左子树高度为3，右子树高度为2，符合AVL树的特点；而右边的树其根节点左子树高度为3，右子树...