树是非常常见的一种数据结构,有着广泛的应用,而二叉树又是树中最最常见的树,值得好好的学习和总结。 树的定义可以参考这里,二叉树Binary Tree的定义在这里,还有二叉搜索树Binar Search Tree。
二叉树特点
如果节点数量是n,那么高度或者说深度h,那么h至少是logn,最大会是n,节点的位置可以参考 题 655. 输出二叉树 BFS/DFS ,这题有树的高度和每个节点的详细信息。
反过来说如果知道树的高度h,那么节点数目至少是h,至多是2h-1。给定一颗树,求树的深度复杂度是O(logn)。
另外一类问题是,对节点进行编号以方便进行某些计算,这时可以以存在的节点为准而,常见的办法是从父节点往子节点编号,比如父节点编号为i,那么其左子节点就是i*2,而右子节点就是i*2+1。从根节点自上而下,根节点肯定 是0,这样每一层都能从0开始做好编号,且不会重复。如题 662. 二叉树最大宽度
二叉树的特性相关问题
题目 | 题解 | 说明 |
---|---|---|
104. 二叉树的最大深度 | 题解 | |
110. 平衡二叉树 | 题解 | |
111. 二叉树的最小深度 | 题解 | |
222. 完全二叉树的节点个数 | 题解 | |
题解 | ||
题解 | ||
题解 |
二叉树的常规遍历
二叉树的常规遍历,其实也是深度优先遍历,分为三种先序,中序和后序。这里的所谓的前中后,是指子节点相对于根节点而言的。对于一个最小的二叉树,也就是只有一个左子节点和右子节点的树来说,先序,就是左右子节点在根节点之后,也即根在最前面,中序就是根在左右中间,而后序则是根在最后。以这个『1, 2, 3』为倒的最小树来说,前序即是[1, 2, 3],中序是[2, 1, 3]而后序 是[2, 3, 1]。
左子节点总是在右子节点前面,左子树总是在右子树前面的,且从整体树来看,遍历的顺序仍旧是从左下到右下,所以需要先找到最左下的一颗最小子树。
递归式
迭代式
逆序遍历
前面说了,二叉树的常规遍历仍旧是从左下向右下的,如果看成数组,那就相当于是从前往后的。但有些情况吧,逆序遍历会更方便,也跟数组一样,有时候从后向前遍历更为合适。逆序遍历并不难,只需要把左右子树的处理换个位置就行了,先找到最右下的最小子树,从右下往左下走。
典型题目
二叉树的层序遍历
也即是广度优先遍历,但普通的广度优先一般没啥用,实际题目中用的最多是层序遍历。
基础广度优先遍历
借助队列,先把根节点加入队列,利用队列的先进先出特性,从队首取出一个节点,并把它的子节点加入到队尾,直到队列为空为止,这样的遍历顺序 便是 基础的广度优先,但在实际中基本没啥用。
1 2 3 4 5 6 7 8 9 10 11 |
|
层序遍历
树的特点是一层是父节点,一层是子节点,知道了父节点层,就能找到子节点层,要想对子节点层做操作必须知道其父节点层。因此层序遍历在实际题目中应用很广泛。
如何能知道每一层呢?其实如果能知道一层,就能知道其下一层,它们是递进的关系,也就分开了。幸运的是我们知道第一层(或者说最上面一层)对,它就是根节点,从它开始,就能找出每一层。具体的做法可以用计数法,计算每层的节点数,用以分 开;也可以用双队列法,一层存放父节点,一层存放子节点,然后交换两个列表,个人喜欢使用双队列法。
具体可以参考以下文章,以及题目中的题解都比较详细,就不重复了。
典型题目
路径相关问题
路径定义不尽相同,有些路径是从根节点到叶子的算路径,有些则不必,前面说的都是竖着的路径,也就是从根节点出发到叶子节点,而有些则可以横着的,比如从左子节点经过根节点到右边节点的路径。路径相关的问题很多,且难度上升级一个量级,通常涉及动态规划。
典型问题
题目 | 题解 | 说明 |
---|---|---|
129. 求根节点到叶节点数字之和 | 题解 | |
257. 二叉树的所有路径 | 题解 | |
112. 路径总和 | 题解 | |
113. 路径总和 II | 题解 | |
124. 二叉树中的最大路径和 | 题解 | |
543. 二叉树的直径 | 题解 | |
236. 二叉树的最近公共祖先 | 题解 | |
1123. 最深叶节点的最近公共祖先 | 题解 | |
题解 | ||
题解 |
二叉搜索树
二叉搜索树Binary Search Tree(常简称作BST),是一种特殊的二叉树,它保证左子树小于根节点小于右子树,如果以中序遍历BST得到的会是一个严格递增的序列。
BST是一个严格递增的序列,这就是BST的本质,与BST有关的题都要应用二分查找:从根节点开始,目标值等于当前节点值,就找到目标了,小于节点值就向左找,大于就向右找。写成代码就是这样:
1 2 3 4 5 6 7 8 9 10 11 |
|
这与二分查找是一样的,这就是BST的本质,深刻理解 了它的本质后,一切问题都会迎刃而解。