数据结构之二叉树的练习题
1.二叉树的前序遍历
题目：给你二叉树的根节点
root，返回它节点值的 前序 遍历。输入：root = [1,null,2,3]
输出：[1,2,3]
这个前序遍历和前文自己写的遍历的不同点：他的返回值是一个List集合，需要用到动态数组来保存元素，而不是简单的打印。
这道题的数组创建要变为成员变量，不能放在方法中，要不每次递归的时候都会开辟一个子数组，答案就不对了
class Solution {
//要注意一点，在leetcode上做题，成员变量和方法不能使用static关键字
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null){
return list;
}
//先根
list.add(root.val);
//递归访问左子树
preorderTraversal(root.left);
//递归访问右子树
preorderTraversal(root.right);
return list;
}
}
2.二叉树的中序遍历
给定一个二叉树的根节点
root，返回 它的 中序 遍历 。输入：root = [1,null,2,3]
输出：[1,3,2]
和前序遍历类似
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null){
return list;
}
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
return list;
}
}
3.二叉树的后序遍历
给你一棵二叉树的根节点
root，返回其节点值的 后序遍历 。输入：root = [1,null,2,3]
输出：[3,2,1]
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null){
return list;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
list.add(root.val);
return list;
}
}
4.相同的树
给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
输入：p = [1,2,3], q = [1,2,3]
输出：true
思路：理解语义，这个函数的作用就是判断树是否相同
一共分三种情况
- 当两颗子树都为空，一定是相同的，返回true
- 当一颗为空，一颗不为空，一定是不相同的，返回false
- 当两棵树都不为空，先判断根节点的值是否相同，在利用子函数递归访问左子树看是否相同，在利用子函数在递归访问右子树是否相同，只有当这三个条件都满足了，我们才认为这两颗树是相同的树，返回true
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null){
return false;
}
return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
5.另一棵树的子树
题目：给你两棵二叉树 root 和 subRoot 。
检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
如果存在，返回 true ；否则，返回 false 。输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
思路：三种情况
- 当两颗子树都为空，一定是相同的，返回true
- 当一颗为空，一颗不为空，一定是不相同的，返回false
- 当两棵树都不为空，利用第4题判断是否为相同树的函数。先判断从两棵树根节点出发是否为相同的树，若不是，在递归访问左子树找是否有和subRoot相同的树，最后，在递归访问右子树找是否有和subRoot相同的树。只要三者满足其一，就表示找到了，返回true。
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null){
return false;
}
return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null){
return false;
}
return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
6.平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
输入：root = [3,9,20,null,null,15,7]
输出：true
思路：这道题也是递归思想。
- 当树为空，返回true
- 既然定义是高度差不超过1，那我们就需要求每个结点的高度差。先求出以根结点为起点，左子树的最大深度，在求出右子树的最大深度。左右子树的差值的绝对值<=1,就说明以根节点为起点的左右子树是平衡的。
- 后面需利用子函数递归求出每个结点的左右子树高度差。
- 每个结点都需要满足高度差<=1,才是一颗平衡二叉树。
这里需要求最大深度，也是利用递归
- 当树为空，返回0
- 当只有根节点，返回1
- 当左右子树都存在，先利用子函数递归的访问左子树求它的最大深度，再利用子函数递归访问右子树求最大深度。
- 利用max()函数找出左右子树升读的最大值，再加上1（根节点），就是整棵树的最大深度了。
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
int abs = Math.abs(left - right);
return abs <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int maxDepth(TreeNode root) {
if (root == null){
return 0;
}
return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
}
7.对称二叉树
题目：
给你一个二叉树的根节点
root， 检查它是否轴对称。输入：root = [1,2,2,3,4,4,3]
输出：true
思路：轴对称就是以中间为轴，左子树翻转到右边和右子树翻转到左边是完全相同的结构
边界：
- 左子树和右子树都为空，对称
- 左子树和右子树一个为空，一个不为空，不对称
满足条件
左子树的树根和右子树的树根是否相等
左子树的左树和右子树的右树是否镜像相等，交给子函数
左子树的右树和右子树的左树是否镜像相等，交给子函数
当上述三个条件都满足，说明这棵树是对称的
public boolean isSymmetric(TreeNode root) {
if (root == null){
return true;
}
//传入两个子树，判断这两颗树是否镜像相等
return isMirror(root.left,root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
//边界
if (t1 == null && t2 == null){
return true;
}
if (t1 == null || t2 == null){
return false;
}
return t1.val == t2.val && isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left);
}
8.二叉树的完全性检验
给定一个二叉树的
root，确定它是否是一个 完全二叉树 。输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
思路：一般判断问题，采用的都是找反例的方式，这道题有两种情况
- 若二叉树中某个节点只有右树没有左树，返回false
- 若二叉树中有一个结点的度为一，且这个结点只有左子树没有右子树，那这个结点有且只有一个。
一共分为两个阶段，引入标志位
- 第一阶段：这个阶段，每个节点都有左右子树；当碰到第一个只有左子树没有右子树的结点或者是叶子结点，切换状态，进入第二阶段。
- 当碰到一个节点只有右树没有左树，反例，false
- 第二阶段：该阶段下，每个节点都是叶子节点，若在第二阶段下发现了有结点右子树，返回false
第二种情况图
public boolean isCompleteTree(TreeNode root) {
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 判断是否是第二阶段
boolean isSecondStep = false;
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (!isSecondStep) {
// 在第一阶段中，每个节点都必须存在左右子树
if (cur.left != null && cur.right != null) {
queue.offer(cur.left);
queue.offer(cur.right);
}else if (cur.left != null) {
// 此时只有左树没有右树，转阶段
isSecondStep = true;
queue.offer(cur.left);
}else if (cur.right != null) {
// 只有右树没左树，反例
return false;
}else {
// 碰到叶子结点，转阶段
isSecondStep = true;
}
}else {
// 此时处在第二阶段，所有节点都必须为叶子结点。
if (cur.left != null || cur.right != null) {
// 不是叶子结点，反例
return false;
}
}
}
return true;
}
9.二叉树的前序遍历
前序遍历的非递归写法（迭代）
给你二叉树的根节点
root，返回它节点值的 前序 遍历。
思路：利用栈这个结构，循环将节点压入栈。当结点有左右子树，先将右子树压入栈，再将左子树压入栈。将当前节点弹出栈并加入到数组中；若没有左右子树，直接弹出栈；若只有一颗子树，将子树压入栈。当栈为空的时候，遍历结束。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null){
return ret;
}
Deque<TreeNode> stack = new LinkedList<>();
//先压入根节点
stack.push(root);
while (!stack.isEmpty()){
TreeNode cur = stack.pop();
ret.add(cur.val);
if (cur.right != null){
stack.push(cur.right);
}
if (cur.left != null){
stack.push(cur.left);
}
}
return ret;
}
10.二叉树的中序遍历
给定一个二叉树的根节点
root，返回 它的 中序 遍历 。迭代
思路：利用栈这个结构，循环将节点压入栈。先访问左子树，在访问右子树，当节点是第二次访问的时候，将这个节点加入到数组中。当结点是第三次访问了，将这个结点弹出栈。当栈为空的时候，遍历结束。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null){
return ret;
}
Deque<TreeNode> stack = new LinkedList<>();
//指针指向根节点
TreeNode cur = root;
while(cur !=null || !stack.isEmpty()){
//一路向左走到底
while (cur != null){
stack.push(cur);
cur = cur.left;
}
//cur为空，弹出栈顶元素
cur = stack.pop();
ret.add(cur.val);
//访问右子树
cur = cur.right;
}
return ret;
}
11.二叉树的后序遍历
给你一棵二叉树的根节点
root，返回其节点值的 后序遍历 。迭代
思路：第三次访问根节点才能遍历
- 一路向左走，此时栈顶就是第一个左子树为空的结点
如何得知这个结点时第三次访问到？
此时引入新的变量prev：指上一个完全访问结束的结点，表示当前节点的右子树是否被处理完毕
当cur.right != null && prev != cur.right 此时cur的右树不为空并且还没被访问完毕
当cur.right != null && prev == cur.right 此时右子树已经处理完毕，将cur弹出并输出节点值
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) {
return ret;
}
TreeNode cur = root;
Deque<TreeNode> stack = new ArrayDeque<>();
// 上一个完全处理完毕的节点.
TreeNode prev = null;
while (cur != null || ! stack.isEmpty()) {
// 1.先一路向左走到底
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
// 2.查看当前栈顶元素的情况
cur = stack.pop();
// 检查右子树的情况
if (cur.right == null || cur.right == prev) {
// 此时右子树为空或者右子树已经被处理完毕
ret.add(cur.val);
// cur节点就是最新的处理结束的结点
prev = cur;
// 继续从栈中取出栈顶元素
cur = null;
}else {
// 此时cur.right != null 且没被访问过，继续访问右子树
stack.push(cur);
// 继续访问右子树
cur = cur.right;
}
}
return ret;
}
12.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
思路：假设一个结点为p，一个结点为q
祖先节点：包括父节点和上层结点，一个节点也可以是它自己的祖先。从祖先节点出发，当前节点处在祖先的树中。
最近祖先：距离最靠近的祖先
公共祖先：从某个节点开始，能同时找到q和p这两个结点。
最近公共祖先：从公共祖先中，深度最大的结点。
从根节点开始向下走，某个节点后序遍历能同时找到q和p两个结点，那么这个结点就是p和q的祖先。
q和p可能出现在三个位置的两个
两个出现在左子树
有一个时根结点
两个都出现在右子树
此时当前结点就是q和p的公共祖先
最终过程：
先找两个节点的所有公共祖先
将当前祖先和它的深度保存在Map集合中，遍历这个树的每个节点，遍历结束后，Map中保存在公共祖先和它的深度。
返回最大深度的那个结点，就是最近公共祖先
两个结点的最近公共祖先特点
p和q这两个结点会出现在当前节点的三个位置中的两个（p和q不在一棵子树中）
左子树
根
右子树
class Solution {
// 最近公共祖先
private TreeNode lca;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 从树中每个节点开始遍历找p和q这两个节点
findNode(root, p, q);
return lca;
}
/**
* 从当前以root为树根的结点开始出发，能否找到p或者q，找到一个就return true
* @param root
* @param p
* @param q
*/
private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return false;
}
// 返回1说明，此时从左子树中至少找到了一个节点
int left = findNode(root.left,p,q) ? 1 : 0;
// 返回1说明在右子树中也至少找到了节点
int right = findNode(root.right,p,q) ? 1 : 0;
// 当前树根就是p或者q的其中一个
int mid = (root == p || root == q) ? 1 : 0;
if (left + right + mid == 2) {
// 此时p和q出现在以root为根的两个位置，这个root一定是lca!!!
lca = root;
}
// 大于0，说明至少找到一个节点
return (left + right + mid) > 0;
}
}
13.[二叉树遍历](二叉树遍历_牛客题霸_牛客网 (nowcoder.com))
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
实例：
输入：
abc##de#g##f###
输出：
c b e g d f a
图示
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HFLhfeU4-1653136710036)(D:\个人\比特\火箭\博客\数据结构之二叉树的练习题\8B986086A8F545819E0C42A24892C415.png)]
先序：ABCDEGF
中序：CBEGDFA
这道题是ACM模式编程
- 所有ACM模式，核心代码都放在类名称为Main，所有核心逻辑都在main中
- 需要手动导入包
- 要注意输入输出的格式问题
class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main{
// 表示当前处理到先序遍历的位置
private static int index = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
// 从外部获取了一个先序遍历的结果集字符串
// abc##de#g##f###
String str = scanner.nextLine();
// 就按照先序遍历的方式还原这个二叉树，返回根节点
TreeNode root = preOrderBuild(str);
// 按照中序遍历的方式输出二叉树的节点值
inOrder(root);
System.out.println();
index = 0;
}
}
/**
* 按照中序遍历遍历二叉树，打印节点值
* @param root
*/
private static void inOrder(TreeNode root) {
if (root == null) {
return;
}
// 先递归左子树
inOrder(root.left);
// 根 需要在一行
System.out.print(root.val + " ");
// 最后递归访问右子树
inOrder(root.right);
}
/**
* 传入一个字符串str，按照先序遍历的方式还原为二叉树，返回二叉树的根节点
* @param str
* @return
*/
private static TreeNode preOrderBuild(String str) {
// 读取一个字符
// abc##de#g##f###
char cur = str.charAt(index);
if (cur == '#') {
// 空树，无需创建节点
return null;
}
TreeNode root = new TreeNode(cur);
index ++;
root.left = preOrderBuild(str);
index ++;
root.right = preOrderBuild(str);
return root;
}
}
14.从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
思路：首先两种遍历的特点：
前序遍历的第一结点就是根节点
中序遍历以根节点为中心区分左右子树
- 先从前序遍历中取出当前树的树根
- 在中序遍历中找到树根所在的位置pos
- 所有左子树节点值[left,pos)
- 所有右子树节点值[pos + 1,right]
- 递归上述过程
- 当前序遍历的每个值都取出，构建结束
核心：
- 使用index表示当前前序遍历处理到哪个结点
- 从前序遍历中取出节点值作为当前树的数根节点
- 找到中序遍历中数根节点的位置pos。[left,pos - 1]就是左子树；[pos + 1,right]就是右子树
- 递归上述过程，当前序遍历的结点全都处理完了，程序结束
class Solution {
//表示处理到前序遍历的位置
private int index = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeHelper(preorder,inorder,0,inorder.length - 1);
}
/**
* 每次从前序遍历中取出树根值，借助中序遍历的[left,right)还原二叉树，返回树的树根
* @param preorder
* @param inorder
* @param left
* @param right
* @return
*/
private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
if (left > right){
//空区间，无任何结点
return null;
}
if (index == preorder.length){
//前序遍历元素全都访问完毕，退出程序
return null;
}
//从前序遍历中取出当前树的数根节点
TreeNode root = new TreeNode(preorder[index]);
index ++;
int pos = find(root.val, inorder);
root.left = buildTreeHelper(preorder,inorder,left,pos - 1);
root.right = buildTreeHelper(preorder,inorder,pos + 1,right);
return root;
}
/**
* 在中序遍历中找到val对应的索引位置
* @param val
* @param inorder
* @return
*/
private int find(int val, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == val){
return i;
}
}
return -1;
}
}
16.从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
思路：后序遍历是左右根，将其转置，就变为了根右左
举例：后序遍历 9 15 7 20 3
转置： 3 20 7 15 9
和上面的套路一致，将其转置后，先递归构建右子树，在递归构建左子树。其余步骤都是一致的。
* 每次从后续遍历中取出树根值，借助中序遍历的[left,right)还原二叉树，返回树的树根
* @param postorderRv
* @param inorder
* @param left
* @param right
* @return
*/
private TreeNode buildTreeHelper(int[] postorderRv, int[] inorder, int left, int right) {
if (left > right){
//空区间，无任何结点
return null;
}
if (index == postorderRv.length){
//后序遍历元素全都访问完毕，退出程序
return null;
}
//从后序遍历中取出当前树的数根节点
TreeNode root = new TreeNode(postorderRv[index]);
index ++;
int pos = find(root.val, inorder);
root.right = buildTreeHelper(postorderRv,inorder,pos + 1,right);
root.left = buildTreeHelper(postorderRv,inorder,left,pos - 1);
return root;
}
/**
* 在中序遍历中找到val对应的索引位置
* @param val
* @param inorder
* @return
*/
private int find(int val, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == val){
return i;
}
}
return -1;
}
}
17.二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
输入描述：
二叉树的根节点
返回值描述：
双向链表的其中一个头节点。
思路：二叉搜索树的特点是：左子树的值 < 根结点值 < 右子树的值
将二叉搜索树进行中序遍历就能得到一个非递减序列。上图中序遍历之后的结果：4 6 8 10 12 14 16。正好是链表的顺序。
二叉树和双向链表的定义
TreeNode{
int val;
TreeNode left;
TreeNode right;
}
Node{
int val;
Node prev;
Node next;
}
- 先中序遍历二叉搜索树
- 转变后的TreeNode的left指向前驱结点，right指向后继节点。
- 先转变左子树，连接树根，后转变右子树。
public class ConvertTree2List {
/**
* 传入任意一棵树的树根节点root，就能将这棵BST转为排序后的双向链表，返回链表的头结点
* @param pRootOfTree
* @return
*/
public TreeNode Convert(TreeNode pRootOfTree) {
// 边界
if(pRootOfTree == null) {
return null;
}
// 1.先将左子树转为排序后的双向链表
TreeNode leftHead = Convert(pRootOfTree.left);
// 2.找到l1链表的尾结点和当前的树根拼接
TreeNode leftTail = leftHead;
while (leftTail != null && leftTail.right != null) {
leftTail = leftTail.right;
}
// leftTail走到了l1的尾结点
// 这里判空的原因左子树就是个空树
if (leftTail != null) {
// 进行拼接
pRootOfTree.left = leftTail;
leftTail.right = pRootOfTree;
}
// 此时l1和root连接起来了
// 3.再将右子树也转为双向链表
TreeNode rightHead = Convert(pRootOfTree.right);
// 将l2的头结点和root拼接
if (rightHead != null) {
rightHead.left = pRootOfTree;
pRootOfTree.right = rightHead;
}
// 返回链表的开始节点。
return leftHead == null ? pRootOfTree : leftHead;
}
}
18.根据二叉树创建字符串
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
输入：root = [1,2,3,4]
输出：“1(2(4))(3)”
解释：初步转化后得到 “1(2(4)())(3()())” ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
思路：省略括号：
当树的左子树不为空，右子树为空可以省略右子树的括号
当树的左右子树都为空，左右子树的括号都可以省略
当左树为空，右树不为空，则左子树的括号不能省略
class Solution {
private StringBuilder sb = new StringBuilder();
public String tree2str(TreeNode root) {
if (root == null) {
return "";
}
// 1.先处理根节点
sb.append(root.val);
// 2.处理左子树
if (root.left != null) {
// 1(2....)
sb.append("(");
// 左子树的转换问题交给子函数
tree2str(root.left);
sb.append(")");
}else {
// 左子树此时为空且右子树不为空，补上一个()
if (root.right != null) {
sb.append("()");
}
}
// 3.处理右子树
if (root.right != null) {
sb.append("(");
// 右子树的内容交给子函数
tree2str(root.right);
sb.append(")");
}
return sb.toString();
}
}