快速搭建网站框架的工具,印度做爰免费网站视频,新网域名自助管理平台,网站开发很难么目录 1. 检验两棵树是否相同
编辑 1. 题目解析
2. 解题步骤
2.判断一棵大树中是否包含有和一棵小树具有相同结构和节点值的子树
1. 题目解析
2. 解题步骤
3. 翻转二叉树
1. 题目解析
2.解题步骤
4. 判断一颗二叉树是否是平衡二叉树
1. 题目解析
2. 解题步骤…目录 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. 解题步骤 假设 pq 两个根节点所在的二叉树的节点个数分别为mn
则 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 所代表的二叉树的节点个数分别为 rs 那么isSubtree() 的时间复杂度为O(r*s)。 3. 翻转二叉树 1. 题目解析 解决这一题我们只需要每次递归的时候如果当前递归的树是一棵空树则不用翻转否则将左右节点的位置互换即可达到翻转的效果 。 2.解题步骤 最好在处理一下root是叶子节点的情况以减少递归次数优化消耗内存分布 4. 判断一颗二叉树是否是平衡二叉树 1. 题目解析 平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1
对于这道题如果我们需要从下往上依次判断当前root的所有节点的左右子树的深度是否相差不超过 1 2. 解题步骤 当前节点的左右子树高度差不超过1 递归左节点的子树为true 递归右节点的子树为true
比较两种情况就能发现
图二return true的条件必须是rootroot.leftroot.right三个节点的左右树高度差不超过1
图一仅仅只是root的左右子树高度差不超过1 5. 对称二叉树 1.题目解析 下图左边的二叉树结构一致但是值不同所以左边的二叉树不是轴对称二叉树 2.解题步骤 6.二叉搜索树与双向链表 1.题目描述 2.解题思路 1.我们观察二叉搜索树和链表可以发现链表节点的顺序就是二叉搜索树通过中序遍历得到的节点顺序。
小知识中序遍历遍历二叉搜索树得到的顺序就是二叉树所有节点从小到大的排序
所以在接下来的做题中我们要先模拟实现一个中序遍历的方法 2. 对于双向链表每一个节点都会有 valprevnext三个域怎么确定每一个二叉树节点转换成链表节点时的 prev域next域也是一个重要的难点。
因为是用二叉树模拟链表所以我们用二叉树节点的 left 模拟 prev 域用 right 模拟 next 域 3.解题步骤
先模拟实现一个中序遍历的方法 此时我们需要对 1节点 进行修改让 root.leftnullroot.right2节点 并且我们在写完对当前root的调整后程序会走到下一行对root.right进行递归的代码此时root.left又一次被修改成null相当于写死了这个问题我们又该怎么改进呢 改进方法很巧妙先在方法外设置prevnull把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);}
}
