建设部网站官网建筑施工合同,浙江省城乡和建设厅网站首页,竞价推广论坛,怎样做网站认证文本目录#xff1a;
❄️一、习题一(检查两颗树是否相同)#xff1a; ▶ 思路#xff1a; ▶ 代码#xff1a; ❄️二、习题二(另一棵树的子树)#xff1a; ▶ 思路#xff1a; ▶ 代码#xff1a; ❄️三、习题三(翻转二叉树)#xff1a; ▶ 思路#xff1a; ▶ 代…文本目录
❄️一、习题一(检查两颗树是否相同) ▶ 思路 ▶ 代码 ❄️二、习题二(另一棵树的子树) ▶ 思路 ▶ 代码 ❄️三、习题三(翻转二叉树) ▶ 思路 ▶ 代码
❄️四、习题四(对称二叉树) ▶ 思路 ▶ 代码
❄️五、习题五(平衡二叉树) ▶ 思路 ▶ 代码 ❄️六、习题六(二叉树的构建和遍历) ▶ 思路 ▶ 代码 ❄️七、总结 ❄️一、习题一(检查两颗树是否相同) ☑ 题的链接 相同的树 ▶ 思路 这个题呢我们需要判断 两个二叉树的结构是否相同并且节点的值是否相同所以呢我们遍历二叉树来看看 两个二叉树的所对应的结构和节点数值是否相同。 我们在结构上呢我们有两种情况
第一种p 这个二叉树对应的节点不为空q 这个二叉树对应的节点为空。
第二种p 这个二叉树对应的节点为空q 这个二叉树对应的节点不为空。 当我们这两个二叉树所对应的节点结构是都为空或这都不为空的时候呢就是我们的结构是一样的之后我们再来判断这两个节点所对应的值是否相同。 所以呢我们是先来判断结构是否相同之后判断节点的值是否相同。 这里呢我们也使用的是递归方法。我们来看看思路图 ▶ 代码 接下来我们来看看代码的编写
public boolean isSameTree(TreeNode p, TreeNode q) {//先判断p和q的结构if (p ! null q null || p null q ! null) {//结构出现错误return false;}//可能是因为都为null或者都不为空//都为空下if (p null q null) {return true;}//都不为空//判断对相应的节点的值是否一样if (p.val ! q.val) {return false;}//走到这就是这个节点判断完成并且是相同的我们之后去其左子树和右子树检查return isSameTree(p.left,q.left) isSameTree(p.right,q.right);//我们递归正确返回的是真} ❄️二、习题二(另一棵树的子树) ☑ 题的链接 另一棵树的子树 ▶ 思路 我们的这道题呢和我们的上面的代码是有关系的我们这到题呢也是需要对于节点的结构和对应的节点值进行比较当我们在 root 里面遍历当我们的遍历出和我们的 subRoot 这个根结点相同的时候呢我们进行 root 和 subRoot 共同遍历在我们没有比较出和 subRoot 根结点相同之前呢我们只有 root 遍历。
判断子树和当前的 root 的左子树一样
判断子树和当前的 root 的右子树一样 ▶ 代码
我们来看看代码是如何实现的
public boolean isSameTree(TreeNode p, TreeNode q) {//先判断p和q的结构if (p ! null q null || p null q ! null) {//结构出现错误return false;}//可能是因为都为null或者都不为空//都为空下if (p null q null) {return true;}//都不为空//判断对相应的节点的值是否一样if (p.val ! q.val) {return false;}//走到这就是这个节点判断完成并且是相同的我们之后去其左子树和右子树检查return isSameTree(p.left,q.left) isSameTree(p.right,q.right);//我们递归正确返回的是真}//另一棵树的子树public boolean isSubtree(TreeNode root, TreeNode subRoot) {if (root null) {return false;}if (isSameTree(root,subRoot)) {return true;}if (isSubtree(root.left,subRoot)) {return true;}if (isSubtree(root.right,subRoot)) {return true;}return false;} ❄️三、习题三(翻转二叉树) ☑ 题的链接 翻转二叉树 ▶ 思路 这道题呢还是非常简单的我们只需要把根的左子树和右子树进行替换之后我们遍历我们的左子树和右子树再执行替换操作。我们来看看思路 ▶ 代码
我们来看看代码如何编写的
public TreeNode invertTree(TreeNode root) {if (root null) {return null;}//进行当前根的左子树和右子树的替换TreeNode cur root.left;root.left root.right;root.right cur;//到根的左子树和右子树去替换//这里用遍历invertTree(root.left);invertTree(root.right);return root;} ❄️四、习题四(对称二叉树) ☑ 题的链接 对称二叉树 ▶ 思路 我们这道题呢和我们判断 两棵树是否相等 是相类似的我们什么情况下我们的二叉树是对称的呢在我们二叉树的 左右子树是在结构上和对应节点的值是相等的时候就是相等的这时候呢我们的二叉树就是对称二叉树。对称二叉树要注意的是我们的左子树的节点应该和右子树的是相等的而不是左子树节点和左子树节点相等。 我们先来看看不为对称二叉树的情况 正确的情况图 所以我们要判断
1、根的左子树是否为空
2、根的右子树是否为空
3、左子树的节点的值和右子树的节点的值是否相等
这里我们要注意的是 我们递归的时候呢我们要判断 左子树的左子树和右子树的右子树。左子树的右子树和右子树的左子树。 ▶ 代码
我们来看看代码
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {//结构不一样的情况下if (leftTree ! null rightTree null|| leftTree null rightTree ! null) {return false;}//在结构一样的情况下左右子树都等于空if (leftTree null rightTree null) {return true;}//在结构一样的情况下左右子树都不等于空//我们来判断左值和右值是否相等if (leftTree.val ! rightTree.val) {return false;}//之后我们来遍历左子树的子树右子树的右子树再次判断是否结构相等和值是否相等return isSymmetricChild(leftTree.left,rightTree.right) isSymmetricChild(leftTree.right,rightTree.left);}public boolean isSymmetric(TreeNode root) {if (root null) {return false;}return isSymmetricChild(root.left,root.right);} ❄️五、习题五(平衡二叉树) ☑ 题的链接 平衡二叉树 ▶ 思路 如果我们想要判断是否是平衡二叉树呢我们的左子树的高度和有字数的高度用需要 2我们不只是需要判断 根结点的高度差是否 2我们需要判断每一颗子树的高度差是否 2如果大于 2 那么就不是平衡二叉树了。 这样理解之后呢就是非常简单的了我们需要使用我们上个博客写的求高度的方法用来求高度去求高度差我们不只是需要判断根节点还需要判断根节点的左子树和根节点的右子树的高度差是否 2 。 ▶ 代码 我们来看看这道题的代码如何编写的 public int getHeight(TreeNode root) {if (root null) {return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);//谁高谁加一return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}//平衡二叉树public boolean isBalanced(TreeNode root) {if (root null) {return true;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);//Math.abs是取绝对值return Math.abs(leftHeight - rightHeight) 2 isBalanced(root.left) isBalanced(root.right);} ❄️六、习题六(二叉树的构建和遍历) ☑ 题的链接 二叉树的构建和遍历 ▶ 思路 我们呢这道题同样使用递归的思想来编写代码这个呢是当我们在遇到 ‘#’ 的时候是为空的我们按照前序遍历来把二叉树进行创建第一个字符为根节点之后我们就按照前序遍历的思想来进行编写代码我们需要一个下标来遍历字符串当遇到字符时候放入二叉树中当为 ‘#’ 时呢节点为空就可以了。所以我们的思路就是
1、先创建根节点
2、创建左子树
3、创建右子树 这个呢就是这道题的思路了我们来看看这个代码是如何编写的 ▶ 代码
import java.util.Scanner;
class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}
}public class Main {public static int i 0;public static TreeNode creatTree(String str) {TreeNode root null;if (str.charAt(i) ! #) {root new TreeNode(str.charAt(i));i;root.left creatTree(str);root.right creatTree(str);} else {i;}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);while (in.hasNextLine()) {String str in.nextLine();TreeNode root creatTree(str);inOrder(root);}}
}
OK我们这道题到这里就结束了。 ❄️七、总结 OK我们这次关于二叉树的习题的练习就到这里就结束了我们在做这种二叉树的题的时候时刻都不要忘记递归的思想。我们呢下篇博客呢还是介绍关于我们二叉树的练习题了让我们尽情期待吧拜拜~~~
