文章目录
- 1. 100.相同的树
- 2. 572. 另一颗树的子树
- 3. 266.翻转二叉树
- 4. LCR 175.计算二叉树的深度
- 5. 110.平衡二叉树
- 6. 101. 对称二叉树
- 7. 牛客题目：KY11 二叉树遍历
- 8. 102.二叉树的层序遍历
- 9. 236.二叉树的最近公共祖先
- 10. 105.根据前序和中序构造一棵二叉树
- 11. 106.根据中序和后序构造一棵二叉树
- 12. 606.根据二叉树创建字符串
- 13. 144.二叉树的前序遍历
- 14. 94.二叉树的中序遍历
- 15. 145.二叉树的后序遍历
1. 100.相同的树
【题目链接】：
100.相同的树
【题目描述】：
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
【解题过程】：
两个二叉树相同，当且仅当两个二叉树的结构完全相同，且所有对应节点的值相同。让两个指针一开始先指向两棵二叉树的根节点，然后同步移动两根指针来同步遍历这两棵树，判断对应位置是否相等。
算法实现步骤：
- 如果两个二叉树中有且只有一个为空，则两个二叉树结构不相同，两棵树一定不相同。
- 如果两个二叉树都为空，则两个二叉树相同。
- 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同
- 若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。
【代码】:
public boolean isSameTree(TreeNode p, TreeNode q) {
//结构上不相同
if(p == null && q != null || p!= null && q==null) {
return false;
}
//结构上相同，此时p、q节点要么同时为null，要么都不为null
if(p == null && q == null){
return true;
}
//此时，p、q都不为null,判断p、q是否相等
if(p.val != q.val) {
return false;
}
//p、q两个根结点相等，然后再判断根节点的左右子树
return isSameTree(p.left,q.left) && isSameTree(p.right ,q.right);
}
复杂度分析：
【时间复杂度】：O(min(m,n))，其中 m 和 n分别是两个二叉树的节点数。只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。
2. 572. 另一颗树的子树
【题目链接】：
572. 另一颗树的子树
【题目描述】：
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
【解题过程】：
遍历root 中的每一个节点，判断这个点的子树是否和 subRoot相等。让两个指针一开始先指向root的节点和 subRoot的根，然后同步移动两根指针来同步遍历这两棵树，判断对应位置是否相等。
算法步骤：
- 首先判断 root和subRoot是否为空，如果为空说明已越过叶节点，因此返回false 。
- 判断两棵树是否相同
- 判断root的左子树和subRoot是否相同
- 判断root的右子树和subRoot是否相同
【代码]:
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null || subRoot == null) {
return false;
}
// 1.首先判断两棵树是否相同
if (isSameTree(root, subRoot)) {
return true;
}
// 2.判断root的左子树和subroot是否相同
if (isSubtree(root.left, subRoot)) {
return true;
}
// 3.判断root的右子树和subroot是否相同
if (isSubtree(root.right, subRoot)) {
return true;
}
// 4.返回结果
return false;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q != null || p != null && q == null) {
return false;
}
// 此时p、q节点要么同时为null，要么都不为null
if (p == null && q == null) {
return true;
}
// 此时，p、q都不为null,判断p、q是否相等
if (p.val != q.val) {
return false;
}
// p、q两个根结点相等，然后再判断根节点的左右子树
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
时间复杂度：假设root含有m个节点，subRoot含有n个节点，对于每一个 root上的点，都需要做一次遍历来和 subRoot匹配，匹配一次的时间代价是 O(n)，那么总的时间代价就是 O(m * n)。故时间复杂度为 O(m * n).
3. 266.翻转二叉树
【题目链接】：
266.翻转二叉树
【题目描述】：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
【解题过程】：
我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果遍历到的节点 root ，就把root节点的左右两棵子树的位置进行交换，直到所有的节点都进行遍历，即可完成以 root 为根节点的整棵子树的翻转。
算法步骤：
- 首先判断 root是否为空，如果为空说明已越过叶节点，因此返回null。
- 判断左子树和右子树是否都为空，都为空（叶子节点）时不进行交换直接返回root。
- 当左右子树都不为空，将根节点的两个引用进行交换
- 采用递归的方式翻转根节点的左子树
- 采用递归的方式翻转根节点的右子树
【代码】:
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
//左子树和右子树都为空
if(root.left == null && root.right == null) {
return root;
}
//左子树和右子树不为null,将左子树和右子树进行翻转
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
//将左子树翻转
invertTree(root.left);
//将右子树翻转
invertTree(root.right);
return root;
}
时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
4. LCR 175.计算二叉树的深度
【题目链接】：
LCR 175.计算二叉树的深度
【题目描述】：
某公司架构以二叉树形式记录，请返回该公司的层级数。
【解题过程】：
关键点： 二叉树的深度和二叉左（右）子树的深度之间的关系。二叉树的深度等于左子树的深度与右子树的深度中的最大值 +1 。
算法步骤：
- 首先判断 root是否为空，如果root为空说明已越过叶节点，因此返回深度0 。
- 计算根节点 root 的 左子树的深度。
- 计算根节点 root 的 右子树的深度。
- 返回二叉树的深度 ，二叉树的深度等于左子树的深度与右子树的深度中的最大值 +1。
【代码】:
public int height(TreeNode root) {
if(root == null) {
return 0;
}
//计算左子树的深度
int leftNode = height(root.left);
//计算右子树的深度
int rightNode = height(root.right);
//二叉树的深度等于左子树的深度与右子树的深度中的最大值 +1
return leftNode > rightNode ? leftNode + 1 :rightNode + 1;
}
时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。
5. 110.平衡二叉树
【题目链接】：
110.平衡二叉树
【题目描述】：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
【解题过程】：
二叉树的根节点的左右子树的高度差的绝对值不超过 1，并且二叉树的左子树和右子树也是平衡的，则说明该二叉树是平衡二叉树。根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树。
算法步骤：
- 首先判断 root是否为空，如果root为空说明已越过叶节点，或者二叉树为空树，是平衡的 。
- 计算根节点 root 的 左子树的深度。
- 计算根节点 root 的 右子树的深度。
- 判断二叉树的根节点的左右子树的高度差的绝对值是否不超过 1，并且二叉树的左子树和右子树也是平衡的，如果都满足则说明该二叉树是平衡二叉树
【代码】:
public boolean isBalanced(TreeNode root) {
//如果root为空说明已越过叶节点，或者二叉树为空树，是平衡的
if (root == null) {
return true;
}
// 获取左右子树的高度
int left = height(root.left);
int right = height(root.right);
//二叉树的根节点的左右子树的高度差的绝对值不超过 1，并且二叉树的左子树和右子树也是平衡的,此时二叉树是平衡的
return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
复杂度分析：
时间复杂度：O(n^2)，其中 n是二叉树中的节点个数。最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，每个节点求高度时的时间复杂度为O(n)，所以总的时间复杂度是 O(n^2)。
【代码优化】：
上述由于是自顶向下递归，因此对于同一个节点，函数 height会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 heightt 只会被调用一次。
优化思想：减少重复高度的计算，一边求高度一边判断是否平衡的问题，
- 先递归地判断其左右子树是否平衡
- 再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −1（不平衡）。
如果左右子树都是平衡的，并且它们之间的高度差小于或等于1，则计算并返回最大高度加1。而如果不平衡，那么就会返回-1。这种方法利用哨兵值（即标志值或特殊值）通过递归向上传播不平衡-1状态。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
public int height(TreeNode root) {
//如果root为空说明已越过叶节点，或者二叉树为空树，是平衡的
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
//如果左子树的高度是-1，那么左子树不平衡
if (leftHeight < 0) {
return -1;
}
int rightHeight = height(root.right);
//如果右子树的高度是-1，那么右子树不平衡
if (rightHeight < 0) {
return -1;
}
//此地左右子树都是平衡的，需要判断当前节点的二叉树是否平衡，
//如果当前节点的左右子树的高度差的绝对值不超过 1，那么该树平衡，返回该二叉树的高度
if (Math.abs(leftHeight - rightHeight) <= 1) {
return Math.max(leftHeight, rightHeight) + 1;
} else {
//如果超过 1，那么该二叉树是不平衡的，返回-1
return -1;
}
}
【复杂度分析】：
时间复杂度：O(n)，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)。
6. 101. 对称二叉树
【题目链接】：
101. 对称二叉树
【题目描述】：
给你一个二叉树的根节点 root ， 检查它是否轴对称。
【解题过程】：
首先，如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，treeLeft指向左子树，treeRight指向右子树，然后进行判断：
- 当左子树存在右子树不存在，或者当右子树存在左子树不存在时不是对称二叉树
- 判断左右子树是否存在，如果左右子树都不存在那么是对称的
- 如果左右子树都存在,首先判断根节点的值是否相同，如果相等再判断左右子树是否对称。由于对称，需要再判断左子树的左子树和右子树的右子树，左子树的右子树和右子树的左子树是否相同
【代码】:
public boolean isSymmetric(TreeNode root) {
//是一颗空的二叉树
if(root == null) {
return true;
}
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode treeLeft,TreeNode treeRight) {
//当左子树存在右子树不存在，或者当右子树存在左子树不存在时不是对称二叉树
if(treeLeft == null && treeRight != null || treeLeft != null && treeRight == null){
return false;
}
//此时，要么左右子树都不存在
if(treeLeft == null && treeRight == null) {
return true;
}
//要么左右子树都存在,首先判断根节点的值是否相同
if(treeLeft.val != treeRight.val) {
return false;
}
//此时，左右子树根节点的值相同，由于对称，需要再判断左子树的左子树和右子树的右子树，左子树的右子树和右子树的左子树是否相同
return isSymmetricChild(treeLeft.left,treeRight.right) && isSymmetricChild(treeLeft.right,treeRight.left);
}
【复杂度分析】：
时间复杂度：假设二叉树一共 n 个节点。这里遍历了这棵树，时间复杂度为 O(n)。
7. 牛客题目：KY11 二叉树遍历
【题目链接】：
KY11 二叉树遍历
【题目描述】：
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
【解题过程】：
根据先序遍历字符串构建二叉树：
- 遍历字符串，使用递归的方式构建二叉树，每次取出字符串中的一个字符，如果是#表示空树，则返回null，否则创建一个新的节点，并递归构建其左子树和右子树。
- 中序遍历顺序：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。 使用递归的方式进行中序遍历，先遍历左子树，然后将当前节点的值添加到结果字符串中，最后遍历右子树。
【代码】:
public class Main {
static class TreeNode {
public char val;
public TreeNode left;//左孩子的引用
public TreeNode right;//右孩子的引用
public TreeNode(char val) {
this.val = val;
}
}
public static int index = 0; //作为字符串遍历时的下标
public static TreeNode createTree(String str){
TreeNode root = null;
if(str.charAt(index) != '#'){
//创建一个新节点
root = new TreeNode(str.charAt(index));
index++;
//构建左子树
root.left = createTree(str);
//构建右子树
root.right = createTree(str);
}else{
index++;
}
//当字符是#表示空树，返回null，不是#时会创建一个新的节点，返回的是该节点
return root;
}
public static void inOrder(TreeNode root) {
if(root == null) {
return;
}
//先遍历左子树
inOrder(root.left);
//将当前节点的值添加到结果字符串中
System.out.print(root.val+" ");
//最后遍历右子树
inOrder(root.right);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();//读取先序遍历字符串
TreeNode root = createTree(str);//构建二叉树
inOrder(root);//中序遍历
}
}
我们并不用考虑，index 是否会越界的情况，因为我们根本没有用 index 来控制循环次数，而是一边前序遍历，一边构建整棵树。
我们设置 index 为静态变量，那么它只适用于一个测试用例，如果有多个测试用例，那么index已经保留了上一个测试用例的值，可能无法正常运行（在力扣上会报错）。所以最好的，我们要把 static 去掉，这样即使有多个测试用例，也可以得到正确结果。
public class Main {
static class TreeNode {
public char val;
public TreeNode left;//左孩子的引用
public TreeNode right;//右孩子的引用
public TreeNode(char val) {
this.val = val;
}
}
public static int index = 0;
public static TreeNode createTree(String str) {
index = 0;//每调用一个实例，就会重置index下标
return createTreeTmp(str);
}
private static TreeNode createTreeTmp(String str) {
TreeNode root = null;
if (str.charAt(index) != '#') {
//创建一个新节点
root = new TreeNode(str.charAt(index));
index++;
//构建左子树
root.left = createTreeTmp(str);
//构建右子树
root.right = createTreeTmp(str);
} else {
index++;
}
//当字符是#表示空树，返回null，不是#时会创建一个新的节点，返回的是该节点
return root;
}
public static void inOrder(TreeNode root) {
if (root == null) {
return;
}
//先遍历左子树
inOrder(root.left);
//将当前节点的值添加到结果字符串中
System.out.print(root.val + " ");
//最后遍历右子树
inOrder(root.right);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();//读取先序遍历字符串
TreeNode root = createTree(str);//构建二叉树
inOrder(root);//中序遍历
}
}
可以使用辅助方法，在每次调用创建二叉树时，提前将index重置为0，在调用辅助方法构建二叉树，即可通过多个测试用例。
8. 102.二叉树的层序遍历
【题目链接】：
102.二叉树的层序遍历
【题目描述】：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
【解题过程】：层序遍历：从上到下、从左到右依次进行遍历
借助队列实现：
- 首先根元素入队
- 当队列不为空的时候，将队列中的元素出队进行打印，出队的同时将出队元素的左右子树的根节点（不为空）进行入队
- 然后进入下一次迭代，直到队列中没有元素
【代码】:
//层序遍历(借助队列)
void levelOrder(TreeNode root) {
//二叉树为空，不打印
if (root == null) {
return;
}
//创建辅助队列
Queue<TreeNode> queue = new LinkedList<>();
//将头节点入队
queue.offer(root);
//迭代打印，直到队列为空
while (!queue.isEmpty()) {
//头节点出队
TreeNode cur = queue.poll();
//如果头节点的左子树的根节点不为空，就将该节点入队
System.out.print(cur.val + " ");
if (cur.left != null) {
queue.offer(cur.left);
}
//如果头节点的右子树的根节点不为空，就将该节点入队
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
使用二元组接受层序遍历的结果：
- 首先创建一个结果列表result来存储层序遍历的结果。
- 创建一个队列queue并将根节点入队。
- 我们使用一个循环来处理每一层的节点。在循环中，我们首先获取当前层的节点数size，然后创建一个列表tmp 来存储当前层的节点值。接着，我们从队列中取出size个节点，将它们的值加入tmp 列表，并将它们的非空子节点加入队列。
- 完成当前层的处理后，我们将tmp列表加入ret列表，然后进行下一层迭代。
- 当队列为空时，我们完成了二叉树的层序遍历。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
//二叉树为空，不打印
if (root == null) {
return ret;
}
//创建辅助队列
Queue<TreeNode> queue = new LinkedList<>();
//将头节点入队
queue.offer(root);
//迭代打印，直到队列为空
while (!queue.isEmpty()) {
//获取一行元素的个数，也就是求一下当前队列的大小
int size = queue.size();
//将每一行的元素放在一个集合中
List<Integer> tmp = new ArrayList<>();
//当size为0时，说明一层元素都出队了，迭代遍历下一层元素
while (size != 0) {
TreeNode cur = queue.poll();
tmp.add(cur.val);
size--;
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
//将存储一行元素的集合存入最终的二元组中
ret.add(tmp);
}
return ret;
}
时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
9. 236.二叉树的最近公共祖先
【题目链接】：
236.二叉树的最近公共祖先
【题目描述】：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
【解题过程】：
解题方法一：
p、q的分布共有以下几种情况：
算法思想：遍历二叉树，遇到p或者q就返回
【代码】:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}
//第1种情况：root是p或者q中的一个，那么结果为root
if(p == root || q == root) {
return root;
}
TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
//第2种情况：左右子树都不为空，结果为root
if(leftTree != null && rightTree != null) {
return root;
//第3种情况：右子树的结果为空，左子树不为空，结果为左子树这个不为空的值
}else if(leftTree != null) {
return leftTree;
//第4种情况：左子树的结果为空，右子树不为空，结果为右子树这个不为空的值
}else{
return rightTree;
}
}
首先检查当前节点是否等于节点p或节点q。如果是，那么当前节点就是最近公共祖先。否则，我们分别在左子树和右子树中递归寻找最近公共祖先。如果左子树和右子树都返回非空节点，那么说明节点p和节点q分别在当前节点的左子树和右子树中，当前节点就是最近公共祖先。如果只有左子树返回非空节点，那么说明节点p和节点q都在左子树中，返回左子树的结果作为最近公共祖先。如果只有右子树返回非空节点，那么说明节点p和节点q都在右子树中，返回右子树的结果作为最近公共祖先。
解题方法二(借用辅助栈)：
使用求链表的交点的方法：
- 将节点p和节点q搜索路径分别存储到两个栈中
2. 让较长的栈先弹出两个栈的长度差个元素
- 同时比较两个栈的栈顶元素，如果不相等则比较下一对栈顶元素，如果相等那么就是最近公共祖先（由上向下遍历二叉树，一定是最近公共祖先）。
该方法难点：如何存储，从根节点到节点p或者节点q的所有节点
就将不是该路径上的节点出栈,直接stack.pop();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
// 将节点p的搜索路径存放在stackP栈中
Stack<TreeNode> stackP = new Stack<>();
getPath(root, p, stackP);
// 将节点q的搜索路径存放在stackQ栈中
Stack<TreeNode> stackQ = new Stack<>();
getPath(root, q, stackQ);
// 让较长的栈先弹出两个栈的长度差个元素
int sizeP = stackP.size();
int sizeQ = stackQ.size();
if (sizeP > sizeQ) {
int size = sizeP - sizeQ;
while (size != 0) {
stackP.pop();
size--;
}
} else {
int size = sizeQ - sizeP;
while (size != 0) {
stackQ.pop();
size--;
}
}
// 同时比较两个栈的栈顶元素
while (!stackP.isEmpty() && !stackQ.isEmpty()) {
if (stackP.peek() == stackQ.peek()) {
return stackP.peek();
} else {
// 如果不相等则比较下一对栈顶元素
stackP.pop();
stackQ.pop();
}
}
return null;
}
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
if (root == null || node == null) {
return false;
}
// 将根节点放入栈中
stack.push(root);
if (root == node) {
return true;
}
// 判断左子树
boolean flg1 = getPath(root.left, node, stack);
if (flg1 == true) {
return true;
}
// 判断右子树
boolean flg2 = getPath(root.right, node, stack);
if (flg2 == true) {
return true;
}
// 代码到这，说明左子树和右子树都没有node节点，将根节点弹出
stack.pop();
return false;
}
10. 105.根据前序和中序构造一棵二叉树
【题目链接】：
105.根据前序和中序构造一棵二叉树
【题目描述】：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
【解题过程】：
先序遍历可以确定根结点的位置，在先序遍历中的第一个节点就是根结点。中序遍历可以确定左右子树，根节点的左边就是左子树，右边的就是右子树的结点。
二叉树创建过程：
算法步骤：
- 在先序遍历中找到根节点
- 根据先序遍历的根节点，在中序遍历结果中找到该节点的位置
- 在中序遍历中根节点的前半部分为左子树，根节点的后半部分为右子树
- 迭代上面的过程构建一颗二叉树
【代码】：
public static int index;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 先序遍历中根节点的下标
index = 0;
TreeNode root = buildTreeChild(preorder, inorder, 0, inorder.length - 1);
return root;
}
private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {
if (inbegin <= inend) {
TreeNode root = new TreeNode(preorder[index]);
// 获取中序遍历中根节点的位置
int getRoot = getPath(inorder, inbegin, inend, preorder[index]);
index++;
// 构建左子树
root.left = buildTreeChild(preorder, inorder, inbegin, getRoot - 1);
// 构建右子树
root.right = buildTreeChild(preorder, inorder, getRoot + 1, inend);
return root;
} else {
return null;
}
}
private int getPath(int[] inorder, int inbegin, int inend, int target) {
for (int i = inbegin; i <= inend; i++) {
if (inorder[i] == target) {
return i;
}
}
return -1;
}
11. 106.根据中序和后序构造一棵二叉树
【题目链接】：
106.根据中序和后序构造一棵二叉树
【题目描述】：
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
【解题过程】：
后序遍历可以确定根结点的位置，在后序遍历结果中的最后一个节点就是根结点。中序遍历可以确定左右子树，根节点的左边就是左子树，右边的就是右子树的结点。
算法步骤：
- 在后序遍历的结果中找到根节点
- 根据后序遍历的根节点，在中序遍历结果中找到该节点的位置
- 在中序遍历中根节点的前半部分为左子树，根节点的后半部分为右子树（先创建右子树，后创建左子树）
- 迭代上面的过程构建一颗二叉树
【代码】：
class Solution {
//根节点的下标
public static int postIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
//后序遍历中第一个根节点的位置
postIndex = postorder.length - 1;
return buildTreeChild(inorder, 0, inorder.length - 1, postorder);
}
private TreeNode buildTreeChild(int[] inorder, int inBegin, int inEnd, int[] postorder) {
if (inBegin > inEnd) {
return null;
}
TreeNode root = new TreeNode(postorder[postIndex]);
// 获取中序遍历中根节点的位置
int getRootIn = getRootIn(inorder, inBegin, inEnd, postorder[postIndex]);
postIndex--;
// 构建右子树
root.right = buildTreeChild(inorder, getRootIn + 1, inEnd, postorder);
// 构建左子树
root.left = buildTreeChild(inorder, inBegin, getRootIn - 1, postorder);
// 返回根节点
return root;
}
private int getRootIn(int[] inorder, int inBegin, int inEnd, int target) {
for (int i = inBegin; i <= inEnd; i++) {
if (inorder[i] == target) {
return i;
}
}
return -1;
}
}
12. 606.根据二叉树创建字符串
【题目链接】：
606.根据二叉树创建字符串
【题目描述】：
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
【解题过程】：
根据题目描述可以分为以下几种情况：
- 从根节点进入，如果根节点不为空打印根节点
- 左子树和右子树为空时直接结束此次递归
- 左子树不为空，右子树为空：先打印（，打印左子树根节点，再打印）
- 左子树为空，右子树不为空：先打印（）
【代码】：
public String tree2str(TreeNode root) {
// 创建一个StringBuilder类型数据存放节点
StringBuilder sb = new StringBuilder();
tree2strChild(root, sb);
// StringBuilder类型数据转换为字符串类型并返回
return sb.toString();
}
public void tree2strChild(TreeNode root, StringBuilder sb) {
if (root == null) {
return;
}
// 先打印根节点
sb.append(root.val);
// 左子树为空
if (root.left != null) {
sb.append("(");
tree2strChild(root.left, sb);
sb.append(")");
} else {
// 左右子树都为空
if (root.right == null) {
return;
// 左右子树都不为空
} else {
sb.append("()");
}
}
// 打印右子树
if (root.right != null) {
sb.append("(");
tree2strChild(root.right, sb);
sb.append(")");
}
}
public String tree2str(TreeNode root) {
StringBuilder sb = new StringBuilder();
tree2strHelper(root, sb);
return sb.toString();
}
private void tree2strHelper(TreeNode root, StringBuilder sb) {
if (root == null) {
return;
}
sb.append(root.val);
if (root.left != null || root.right != null) {
sb.append("(");
tree2strHelper(root.left, sb);
sb.append(")");
}
if (root.right != null) {
sb.append("(");
tree2strHelper(root.right, sb);
sb.append(")");
}
}
力扣给的官方题解:
public String tree2str(TreeNode root) {
if (root == null) {
return "";
}
if (root.left == null && root.right == null) {
return Integer.toString(root.val);
}
if (root.right == null) {
return new StringBuffer().append(root.val)
.append("(")
.append(tree2str(root.left))
.append(")")
.toString();
}
return new StringBuffer().append(root.val)
.append("(")
.append(tree2str(root.left))
.append(")(")
.append(tree2str(root.right))
.append(")")
.toString();
}
13. 144.二叉树的前序遍历
【题目链接】：
144.二叉树的前序遍历
【题目描述】：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
【解题过程】：
使用辅助栈来进行打印：
-
当临时变量遇见根节点不为空时，就将根节点入栈，并打印
-
然后将临时节点变为根节点的左子树，循环判断，当临时变量为空时
-
将临时节点赋值为栈顶元素的右节点，继续循环判断。
- 当栈为空时，打印完毕
【代码】:
//二叉树递归先序遍历
public List<Integer> preorderTraversal(TreeNode root) {
//返回的结果
List<Integer> list = new ArrayList<>();
//临时变量
TreeNode cur = root;
//创建一个辅助栈
Stack<TreeNode> stack = new Stack<>();
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
TreeNode tmp = stack.pop();
cur = tmp.right;
}
return list;
}
//二叉树递归先序遍历
public List<Character> preorderTraversal(TreeNode root) {
List<Character> list = new ArrayList<>();
preorderTraversalChild(root, list);
return list;
}
public void preorderTraversalChild(TreeNode root, List<Character> list) {
if (root == null) {
return;
}
list.add(root.value);
preorderTraversalChild(root.left, list);
preorderTraversalChild(root.right, list);
}
14. 94.二叉树的中序遍历
【题目链接】：
94.二叉树的中序遍历
【题目描述】：
给定一个二叉树的根节点 root ，返回 它的 中序 遍历。
【解题过程】：
使用辅助栈来进行打印：
-
当临时变量遇见根节点不为空时，就将根节点入栈
-
然后将临时节点变为根节点的左子树，循环判断，当临时变量为空时
-
先将栈顶元素打印，再将临时节点赋值为栈顶元素的右节点，继续循环判断。
- 当栈为空时，打印完毕
【代码】：
//二叉树非递归中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
//返回的结果
List<Integer> list = new ArrayList<>();
//临时变量
TreeNode cur = root;
//创建一个辅助栈
Stack<TreeNode> stack = new Stack<>();
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode tmp = stack.pop();
list.add(tmp.val);
cur = tmp.right;
}
return list;
}
//二叉树递归中序遍历
public List<Character> inorderTraversal(TreeNode root) {
List<Character> list = new ArrayList<>();
inorderTraversalChild(root, list);
return list;
}
public void inorderTraversalChild(TreeNode root, List<Character> list) {
if (root == null) {
return;
}
inorderTraversalChild(root.left, list);
list.add(root.value);
inorderTraversalChild(root.right, list);
}
15. 145.二叉树的后序遍历
【题目链接】：
145.二叉树的后序遍历
【题目描述】：
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
【解题过程】：
后序遍历的顺序：左-右-根
代码思路：我们维护一个辅助栈来实现后序遍历
-
使用一个临时变量，并且临时变量一直向左走，同时将节点入栈，直到遇见空时停止
-
使用临时变量top指向栈顶元素
-
此时，栈顶元素的右节点分为两种情况：
-
栈顶元素的右节点为空，那么就弹出栈顶元素，并且打印栈顶元素，同时使用临时变量prev标记栈顶元素，防止二次打印
-
栈顶元素的右节点 不为空，临时变量cur指向栈顶元素的右节点
- 当右边打印完时(top.right = prev)，栈顶元素也要出栈。
【代码】：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
//创建辅助栈
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
//存储上一个栈顶节点,用于判断右边的树是否打印完
TreeNode prev = null;
//当栈为空时，说明所有节点打印完了
while(cur != null || !stack.isEmpty()) {
//一直向左将节点入栈
while(cur != null){
stack.push(cur);
cur = cur.left;
}
//cur为空,向左的所有节点全部入栈了
//获取栈顶节点，用于判断右子树是否打印完
TreeNode top = stack.peek();
//当栈顶元素的右节点和上一次打印的节点相等，或者栈顶元素的右子树为空时，将栈顶元素出栈，并进行打印，并使用prev记录此次打印的节点
if(top.right == prev || top.right == null) {
list.add(top.val);
stack.pop();
prev = top;
}else{
//将右子树的节点入栈
cur = top.right;
}
}
return list;
}
