本系列可作为JAVA学习系列的笔记文中提到的一些练习的代码小编会将代码复制下来大家复制下来就可以练习了方便大家学习。点赞关注不迷路您的点赞、关注和收藏是对小编最大的支持和鼓励系列文章目录JAVA初阶---------已更完JAVA数据结构 DAY1-集合和时空复杂度JAVA数据结构 DAY2-包装类和泛型JAVA数据结构 DAY3-List接口JAVA数据结构 DAY4-ArrayListJAVA数据结构 DAY5-LinkedListJAVA数据结构 DAY6-栈和队列JAVA数据结构 DAY7-二叉树拓展目录手把手教你用 ArrayList 实现杨辉三角从逻辑推导到每行代码详解链表高频 6 题精讲 | 从入门到熟练掌握链表操作二叉树高频题精讲 | 从入门到熟练掌握二叉树操作二叉树高频题精讲 | 从入门到熟练掌握二叉树操作2目录目录系列文章目录拓展目录目录前言1.相同的树2.另一棵树的子树3.翻转二叉树4.平衡二叉树5.对称二叉树6.二叉树遍历7.二叉树的层序遍历8.二叉树最近的公共祖先总结前言小编作为新晋码农一枚会定期整理一些写的比较好的代码作为自己的学习笔记会试着做一下批注和补充如转载或者参考他人文献会标明出处非商用如有侵权会删改欢迎大家斧正和讨论本节我将分享一下二叉树的习题部分以及思路详解在力扣 的运行环境每一题将会附上练题链接大家点击即可练习1.相同的树给你两棵二叉树的根节点p和q编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。题目链接https://leetcode.cn/problems/same-tree/description/提示两棵树上的节点数目都在范围[0, 100]内-104 Node.val 104严格按照先结构 → 后值步骤判断结构都空 → 结构相同 ✅一个空一个不空 → 结构不同 ❌判断值值不同 → 树不同 ❌递归判断左右子树/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { //假设p的节点树为m,q的节点数为n //时间复杂度O(min(m,n)) public boolean isSameTree(TreeNode p, TreeNode q) { //1.先判断结构是否是一样的 if(p!nullqnull||pnullq!null){ return false; } //上述if语句如果没有执行 意味着两个引用同时为空或者同时不为空 if(pnullqnull){ return true; } //都不为空 判断值是否一样 if(p.val!q.val){ return false; } //都不为空且值一样 return isSameTree(p.left,q.left) isSameTree(p.right,q.right); } }2.另一棵树的子树给你两棵二叉树root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在返回true否则返回false。二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。题目链接https://leetcode.cn/problems/subtree-of-another-tree/description/子树 必须包含某个节点 它的所有后代不能少一个也不能多一个也就是说子树的空节点必须和主树某棵子树的空节点 完全对应但是这个情况不是的前半部分确实一样但主树的 2 有右孩子 5子树的 2 没有→结构不一样→isSameTree 返回 false→不是子树//相同的树 //严格按照先结构 → 后值 //步骤 //判断结构 //都空 → 结构相同 ✅ //一个空一个不空 → 结构不同 ❌ //判断值 //值不同 → 树不同 ❌ //递归判断左右子树 public boolean isSameTree(TreeNode root1,TreeNode root2){ if(root1nullroot2null){ return true; } if(root1null||root2null){ return false; } if(root1.val!root2.val){ return false; } return isSameTree(root1.left,root2.left)isSameTree(root1.right,root2.right); } //给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。 // 如果存在返回 true 否则返回 false 。 //二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 public boolean isSubTree(TreeNode root,TreeNode root1){ if(rootnullroot1null){ return true; } if(isSameTree(root,root1)||isSameTree(root.left,root1.left)||isSameTree(root.right,root1.right)) return true; return false; }3.翻转二叉树给你一棵二叉树的根节点root翻转这棵二叉树并返回其根节点。题目链接226. 翻转二叉树 - 力扣LeetCode//给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 public TreeNode binaryTreeInversion(TreeNode root){ if(rootnull){ return null; } TreeNode noderoot.left; root.leftroot.right; root.rightnode; binaryTreeInversion(root.left); binaryTreeInversion(root.right); return root; }4.平衡二叉树给定一个二叉树判断它是否是 平衡二叉树题目链接https://leetcode.cn/problems/balanced-binary-tree/description/写一个求高度方法getHeight判空算左右高度差 1 返回 false递归判断左右子树/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { //获取二叉树的高度 public int nodeHeight(TreeNode root){ if(rootnull){ return 0; } int leftHeightnodeHeight(root.left); int rightHeightnodeHeight(root.right); return Math.max(leftHeight,rightHeight)1; } //判断是否是平衡树 public boolean isBalanced(TreeNode root) { if(rootnull){ return true; } int leftheightnodeHeight(root.left); int rightheightnodeHeight(root.right); if(Math.abs(leftheight-rightheight)1){ return false; } return isBalanced(root.left)isBalanced(root.right); } }5.对称二叉树给你一个二叉树的根节点root 检查它是否轴对称。题目链接101. 对称二叉树 - 力扣LeetCode空树对称✅外侧对称左 ↔ 右✅内侧对称右 ↔ 左✅值必须相等✅//是否是对称二叉树 public boolean isSymmetric(TreeNode root) { if(rootnull){ return true; } return isMirror(root.left,root.right); } public boolean isMirror(TreeNode root1,TreeNode root2){ if(root1nullroot2null){ return true; } if(root1null||root2null){ return false; } if(root1.val!root2.val){ return false; } return isMirror(root1.left,root2.right)isMirror(root1.right,root2.left); }6.二叉树遍历描述编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。输入描述输入包括1行字符串长度不超过100。输出描述可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。# null先序建树根 → 左 → 右index 必须全局每次输入重置为 0import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { //// 静态内部类static修饰 static class TreeNode{ //关键是static public char val; public TreeNode left;//存储左孩子的引用 public TreeNode right;//存储右孩子的引用 public TreeNode(char val){ this.valval; //this.leftnull; //this.rightnull; //默认是null } } public static int index0; public static TreeNode createTree(String str){ char scstr.charAt(index); index; if(sc#){ return null; } TreeNode curNodenew TreeNode(sc); curNode.leftcreateTree(str); curNode.rightcreateTree(str); return curNode; } 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.hasNext()) { String str in.next(); index 0; // 每次重置下标 TreeNode root createTree(str); inOrder(root); System.out.println(); } } }7.二叉树的层序遍历描述给你二叉树的根节点root返回其节点值的层序遍历。 即逐层地从左到右访问所有节点。提示树中节点数目在范围[0, 2000]内-1000 Node.val 1000/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ //一层一层处理 class Solution { public ListListInteger levelOrder(TreeNode root) { ListListInteger resnew ArrayList(); if(rootnull){ return res; } // 1. 创建队列 QueueTreeNode queuenew LinkedList(); queue.offer(root); // 2. 循环遍历 while(!queue.isEmpty()){ int sizequeue.size(); ListInteger curLevelnew ArrayList(); for(int i0;isize;i){ // 取出队首节点 TreeNode curqueue.poll(); curLevel.add(cur.val); // 左孩子不为空入队 if (cur.left ! null) queue.offer(cur.left); // 右孩子不为空入队 if (cur.right ! null) queue.offer(cur.right); } res.add(curLevel); } return res; } }8.二叉树最近的公共祖先描述给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”我们用这棵树A / \ B C / D我们要找D 和 C 的最近公共祖先答案应该是A正式开始跟着我走函数入口lowestCommonAncestor(A, D, C)第一步看 AA 不是 null不是 D不是 C递归查左left lowestCommonAncestor(B, D, C)递归查右right lowestCommonAncestor(C, D, C)先处理左边lowestCommonAncestor(B, D, C)B 不是 null不是 D不是 C递归查左left lowestCommonAncestor(D, D, C)递归查右right lowestCommonAncestor(null, D, C)再处理左边lowestCommonAncestor(D, D, C)D D直接返回 D处理右边lowestCommonAncestor(null, D, C)root null直接返回 null回到 B 节点现在我们有left Dright null判断不是两边都有返回 left → D现在回到 A 的右边lowestCommonAncestor(C, D, C)C C直接返回 C最终回到 A 节点现在我们手里有left Dright Cif (left ! null right ! null) { return root; }左边找到了右边找到了→返回 A流程结束答案就是 Apublic TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(rootnull||rootq||rootp){ return root; } TreeNode leftlowestCommonAncestor(root.left,p,q); TreeNode rightlowestCommonAncestor(root.right,p,q); if(left!nullright!null){ return root; } return left!null?left:right; }总结以上就是今天要讲的内容本文简单记录了java数据结构仅作为一份简单的笔记使用大家根据注释理解您的点赞关注收藏就是对小编最大的鼓励