树专题总结
树是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。
树里的每一个节点有一个值和一个包含所有子节点的列表。从图的观点来看,树也可视为一个拥有 N 个节点和 N-1 条边的一个有向无环图。
二叉树是一种更为典型的树状结构。二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。
1. 树的遍历
1.1 前序遍历
树的前序遍历:访问 ==根节点 -> 左子树 -> 右子树==
Leetcode 144. 二叉树的前序遍历
给定一个二叉树,返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3输出: [1,2,3]
递归方法
1 | public List<Integer> preorderTraversal(TreeNode root) { |
迭代方法
迭代方法需要用一个辅助栈来实现,模拟递归
1 | public List<Integer> preorderTraversal(TreeNode root) { |
1.2 中序遍历
中序遍历:==左子树 -> 根节点 -> 右子树==
Leetcode 94. 二叉树的中序遍历
给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3输出: [1,3,2]
递归方法
1 | public List<Integer> inorderTraversal(TreeNode root) { |
迭代方法
1 | public List<Integer> inorderTraversal(TreeNode root) { |
1.3 后序遍历
后序遍历:==左子树 -> 右子树 -> 根节点==
Leetcode 145. 二叉树的后序遍历
给定一个二叉树,返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3输出: [3,2,1]
递归方法
1 | public List<Integer> postorderTraversal(TreeNode root) { |
迭代方法
后序遍历可以看做前序遍历的逆序列,当前序遍历是 根节点 - 右子树 - 左子树 的时候,因此可以按照前序遍历的方法进行迭代,返回其逆序列。
1 | public List<Integer> postorderTraversal(TreeNode root) { |
1.4 层次遍历
层序遍历就是逐层遍历树结构。
广度优先搜索是一种广泛运用在树或图这类数据结构中,遍历或搜索的算法。 该算法从一个根节点开始,首先访问节点本身。 然后遍历它的相邻节点,其次遍历它的二级邻节点、三级邻节点,以此类推。
在树中进行广度优先搜索时,访问的节点的顺序是按照层序遍历顺序的。
通常,使用队列来辅助做广度优先搜索过程
Leetcode 102. 二叉树的层序遍历
给你一个二叉树,请你返回其按层序遍历得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],3
/ \
9 20
/ \
15 7
返回其层次遍历结果:[
[3],
[9,20],
[15,7]
]
1 | public List<List<Integer>> levelOrder(TreeNode root) { |
1.5 遍历应用
有些题目是通过调整树的遍历顺序来实现特定目标的,基本思想还是树的遍历。
1.5.1 层次遍历变形
Leetcode 103. 二叉树的锯齿形层次遍历
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7],3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下:[
[3],
[20,9],
[15,7]
]
解题思路
本质上还是==层次遍历==,只是每一层的元素添加顺序不同。
1 | public List<List<Integer>> zigzagLevelOrder(TreeNode root) { |
Leetcode 958. 二叉树的完全性检验
给定一个二叉树,确定它是否是一个完全二叉树。
层次遍历,用一个 boolean 变量标记是否遇到空节点,如果空节点后面出现了非空节点,则一定不是完全二叉树。
1 | public boolean isCompleteTree(TreeNode root) { |
Leetcode 199. 二叉树的右视图
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
BFS
层次遍历,将每一层的最后一个节点加入结果列表。
1 | public List<Integer> rightSideView(TreeNode root) { |
DFS
按照 ==根节点 -> 右子树 -> 左子树== 的顺序遍历二叉树,每一层最先访问的就是最右侧的节点
1 | public List<Integer> rightSideView(TreeNode root) { |
1.5.2 根据遍历序列构造二叉树
Leetcode 105. 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:3
/ \
9 20
/ \
15 7
解题思路
前序遍历:根节点 -> 左子树 -> 右子树
中序遍历:左子树 -> 根节点 -> 右子树
根据前序遍历序列,可以将中序序列分为左子树,根,和右子树,然后递归的将其序列分割,建树
1 | public TreeNode buildTree(int[] preorder, int[] inorder) { |
Leetcode 106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:3
/ \
9 20
/ \
15 7
同样地:
后序遍历:左子树 -> 右子树 -> 根节点
中序遍历:左子树 -> 根节点 -> 右子树
后序遍历序列的最后一个元素是根节点,倒序遍历后序遍历序列,将中序遍历序列分为左右子树,递归地构建树。
1 | public TreeNode buildTree(int[] inorder, int[] postorder) { |
2. 递归应用
2.1 路径和
Leetcode 112. 路径总和
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
递归方法
1 | public boolean hasPathSum(TreeNode root, int sum) { |
迭代方法
借助辅助栈模拟递归
1 | public boolean hasPathSum(TreeNode root, int sum) { |
Leetcode 113. 路径总和 II
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
解题思路
与 T112 相区别的是,该题目不仅要判断是否存在一个路径和,还要找到该路径,因此在递归的时候需要将走过的路径记录下来。
1 | public List<List<Integer>> pathSum(TreeNode root, int sum) { |
Leetcode 437. 路径总和 III
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
解题思路
双重递归
1 | public int pathSum(TreeNode root, int sum) { |
Leetcode 124. 二叉树中的最大路径和
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
1 | // 全局最大值 |
2.2 二叉树的性质相关
Leetcode 100. 相同的树
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
1 | public boolean isSameTree(TreeNode p, TreeNode q) { |
Leetcode 101. 对称二叉树
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树
[1,2,2,3,4,4,3]
是对称的。
1 | public boolean isSymmetric(TreeNode root) { |
Leetcode 226. 翻转二叉树
翻转一棵二叉树。
示例:
输入:
4
/ \
2 7
/ \ / \
1 3 6 9输出:
4
/ \
7 2
/ \ / \
9 6 3 1
1 | public TreeNode invertTree(TreeNode root) { |
Leetcode 236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
1 | public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { |
Leetcode 110. 平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
1 | public boolean isBalanced(TreeNode root) { |
Leetcode 404. 左叶子之和
计算给定二叉树的所有左叶子之和。
1 | public int sumOfLeftLeaves(TreeNode root) { |
Leetcode 671. 二叉树中第二小的节点
给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话,那么该节点的值等于两个子节点中较小的一个。
更正式地说,
root.val = min(root.left.val, root.right.val)
总成立。给出这样的一个二叉树,你需要输出所有节点中的第二小的值。如果第二小的值不存在的话,输出 -1 。
1 | public int findSecondMinimumValue(TreeNode root) { |
3. 二叉搜索树
- 本文作者: Kelly Liu
- 本文链接: http://tiantianliu2018.github.io/2020/10/24/树专题总结/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!