二叉树相关OJ题 — 第一弹

目录

1.  检验两棵树是否相同

​编辑 1. 题目解析

2. 解题步骤 

2.判断一棵大树中是否包含有和一棵小树具有相同结构和节点值的子树

1. 题目解析 

2. 解题步骤 

3.  翻转二叉树

1. 题目解析

2.解题步骤

4.  判断一颗二叉树是否是平衡二叉树

1. 题目解析 

2. 解题步骤

5.  对称二叉树

 1.题目解析

​编辑 2.解题步骤

6.二叉搜索树与双向链表

1.题目描述

 2.解题思路

​编辑

3.解题步骤：

7.  二叉树的构建及遍历

 1.题目解析

2.解题思路​编辑

 3.解题步骤

4. 完整代码

---

1.  检验两棵树是否相同

---

 1. 题目解析

---

两棵树相同的条件：两棵树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例2：

根节点相同，但是一个只有左树，一个只有右树，所以这两棵二叉树的结构不相同，因此这两棵树不是相同的二叉树 ；

示例3：

结构相同，节点值不同，所以不是相同的二叉树 。

---

同时遍历两棵树，先判断两棵树结构是否相同，如果结构相同，再判断两棵树的节点值是否相同 

出现左边的两种情况，则说明两棵树结构不相同；出现右边两种情况，则说明两棵树的结构相同。

---

• 我们再更进一步，通过递归，同时遍历两棵树的每一个节点；遍历到的节点，会出现上图的四种情况；

  ---

  只有当前遍历节点出现右边的两种情况，才能继续判断这两个节点的值是否相同；

  ---

  只有节点的结构和值同时相同，我们才可以认为当前遍历的两个节点在两棵二叉树的相同位置，且值相同；

  ---

  只有所有节点相同，才可以认为两棵树相同。

---

2. 解题步骤 

---

假设 p，q 两个根节点所在的二叉树的节点个数分别为m，n；

则 isSameTree() 的时间复杂度为 O( min(m,n) ) 。

---

2.判断一棵大树中是否包含有和一棵小树具有相同结构和节点值的子树

---

 

(通过上图题目中，提示的 root 和 subroot 的范围，说明root 和 subroot ，有可能是两棵相同的二叉树，并且 root 和 subroot 都不可能是一棵空树） 

1. 题目解析 

---

我们需要特别注意一下示例二，示例二这种情况，subroot 不是 root 的子树：

 所以，我们通过前序遍历，遍历 root 和subroot ，判断：

1.当前 subroot 和 root 是否相同?
2.判断 subroot 和当前 root 的左子树相同?
3.判断 subroot 和当前 root 的右子树相同?

通过上面的判断，我们可以利用刚刚写的isSameTree() ，来判断当前递归遍历的 root 所代表的节点的树，和 subroot 树是否相同

---

2. 解题步骤 

---

---

---

假设 root 和subroot 所代表的二叉树的节点个数分别为 r，s ；那么isSubtree() 的时间复杂度为O(r*s)。

---

3.  翻转二叉树

---

 

1. 题目解析

---

解决这一题，我们只需要每次递归的时候，如果当前递归的树是一棵空树，则不用翻转；否则，将左右节点的位置互换，即可达到翻转的效果 。

---

2.解题步骤

---

最好在处理一下，root是叶子节点的情况，以减少递归次数，优化消耗内存分布：

---

4.  判断一颗二叉树是否是平衡二叉树

---

1. 题目解析 

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1；

对于这道题，如果我们需要从下往上依次判断，当前root的所有节点的左右子树的深度是否相差不超过 1

---

2. 解题步骤

---

 

---

当前节点的左右子树高度差不超过1 && 递归左节点的子树为true && 递归右节点的子树为true 

比较两种情况，就能发现：

图二return true的条件，必须是root，root.left，root.right三个节点的左右树高度差不超过1；

图一仅仅只是root的左右子树高度差不超过1 

---

5.  对称二叉树

---

 1.题目解析

下图左边的二叉树，结构一致，但是值不同，所以左边的二叉树不是轴对称二叉树： 

 2.解题步骤

---

---

6.二叉搜索树与双向链表

---

1.题目描述

 2.解题思路

1.我们观察二叉搜索树和链表，可以发现，链表节点的顺序，就是二叉搜索树通过中序遍历得到的节点顺序。

（小知识：中序遍历遍历二叉搜索树，得到的顺序就是二叉树所有节点从小到大的排序）

所以，在接下来的做题中，我们要先模拟实现一个中序遍历的方法

2. 对于双向链表，每一个节点都会有 val，prev，next三个域；怎么确定每一个二叉树节点，转换成链表节点时的 prev域，next域，也是一个重要的难点。

因为是用二叉树模拟链表，所以我们用二叉树节点的 left 模拟 prev 域，用 right 模拟 next 域

3.解题步骤：

先模拟实现一个中序遍历的方法

此时，我们需要对 1节点 进行修改，让 root.left=null，root.right=2节点；

并且，我们在写完对当前root的调整后，程序会走到下一行，对root.right进行递归的代码，此时，root.left又一次被修改成null，相当于写死了，这个问题我们又该怎么改进呢？

改进方法很巧妙，先在方法外设置prev=null，把1节点设置为prev,再改变prev，让perv指向root，后续进行下一行的递归时，中序遍历到的节点就被一 一串联起来。

根据上图，我们已经把二叉树各个节点该如何调整指向的几步代码写好了；

我们可以以二叉树root遍历到 2节点为例子，就会发现：

1节点和2节点的双向关系已经确定好了，并且prev从1节点走到2节点，为下一次递归为2节点和3节点构建关系打下基础。

所以，我们需要处理一下边界情况：

 因为 ConvertChild() 方法仅仅只是把二叉树调整成链表，在 Convert() 方法中，才会返回链表头节点，所以我们可以优化一下，将ConvertChild() 方法的返回值类型修改成 void：

根据代码，将二叉树被转换成链表的过程中，节点指向的调整过程，再仔细地思考一遍。当我们能想明白，上面用中序遍历的顺序，来调整每个节点的指向；并且想清楚调整的方式，就会为之拍案叫绝！

完善Convert() 即可。 

---

7.  二叉树的构建及遍历

---

 1.题目解析

小知识:
如果在遍历二叉树得到的输出结果，没有标出空树的具体位置，是无法通过前序遍历和后序遍历的输出结构还原一棵二叉树的；

题中提供的前序遍历输出结构已经标明空树的位置，我们可以提供输出结果还原二叉树

---

2.解题思路

---

 

 3.解题步骤

 

4. 完整代码

import java.util.Scanner;class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}
}
//我们需要自己定义TreeNode类// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();Main s = new Main();//createTree() 的返回值是创建好二叉树后的头节点，用root接收一下TreeNode root = s.createTree(str);//将root传入inorderTree(),通过中序遍历遍历二叉树，打印节点inorderTree(root);}}//在被static修饰的静态方法中，无法调用成员变量public int i = 0;//创建二叉树public TreeNode createTree(String str) {//如果要通过递归，来拼接字符串，则不需要写循环，i的值通过递归来改变//那么i在下一次递归应该等于上一次递归的值TreeNode root = null;if (str.charAt(i) != '#') {//字符一定要有''root = new TreeNode(str.charAt(i));//分割的字符作为参数，来实例化节点//每次递归，都要通过i++，向后切割stri++;//通过递归拼接节点root.left = createTree(str);root.right = createTree(str);} else {i++;//遍历到的字符为'#'，直接跳过}return root;}//中序遍历打印创建好的二叉树public static void inorderTree(TreeNode root) {if (root == null)return;inorderTree(root.left);System.out.print(root.val + " ");inorderTree(root.right);}
}