找个网站怎么那么难,微网站开发+在线商城,同江佳木斯网站设计,智邦国际erp系统登录目录
1、相同的树
2、另一棵树的子树
3、翻转二叉树
4、平衡二叉树 5、对称二叉树 6、二叉树遍历
7、二叉树的分层遍历 1、相同的树
习题链接https://leetcode.cn/problems/same-tree/description/https://leetcode.cn/problems/same-tree/description/ 描述#xff1a…目录
1、相同的树
2、另一棵树的子树
3、翻转二叉树
4、平衡二叉树 5、对称二叉树 6、二叉树遍历
7、二叉树的分层遍历 1、相同的树
习题链接https://leetcode.cn/problems/same-tree/description/https://leetcode.cn/problems/same-tree/description/ 描述
给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 解题思路 根据题意他要我们判断这两棵树是否相同我们知道要判断两棵树是否相同就是要判断树的结构和对应结点的内容是否相同。 首先我们要来看给我们的两棵树是否是一棵树有结点一棵树没有结点如果是这样的话我们就认为这两棵树不相同同时如果这两颗树的根节点都为空那么我们就认为这两棵树相同。 经历了这两个条件后此时的这两颗树一定是都存在结点这时我们在判断此时的根节点值是否相同如果不同就是不相同的树如果相同我们就继续往下走判断对应的左子树和右子树是否相同在递归的形势下传入两棵树根的左边结点作为新的根节点进行判断同理右边也是一样。在这种情况下完成对两棵树的结构和内容的判断。 完整代码
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p ! null q null || p null q ! null){return false;}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);}
}
2、另一棵树的子树
习题链接https://leetcode.cn/problems/subtree-of-another-tree/https://leetcode.cn/problems/subtree-of-another-tree/
描述
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 解题思路 根据题意他是要我们判断给出的两棵树中一棵是否为另一棵的子树而这个子树是包含某个结点开始和他所有的后代的这样来看其实就是判断一棵树的子树和他给出的另一棵树是否相同。注意如果两棵树从根节点开始就是相同的我们也认为他符合题意 首先我们从根节点开始进行判断我们要先判断我们的根节点是否为空因为在下面我们是要有递归实现的总有一次我们会递归到为空的时候这就代表我们此时的根节点为空,而我们要判断的subRoot这棵树却不为空这就代表了以此时结点为根节点的树是和我们要判断的树是不同的因此我们要返回false.而我们判断的方法就是我们上面写的题相同的树因此我们将根节点传isSameTree进行判断。 当我们判断完根结点后我们要判断跟的左子树因此我们要将根的左结点传入进行递归判断完再判断右树如果都不存在就返回false; 完整代码
class Solution {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 boolean isSameTree(TreeNode p, TreeNode q) {if(p null q ! null || p ! null q null){return false;}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);}
}
3、翻转二叉树
习题链接https://leetcode.cn/problems/invert-binary-tree/description/https://leetcode.cn/problems/invert-binary-tree/description/ 描述给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 解题思路 根据图示我们能发现这道题就是让我们将根的左右结点进行交换说到交换这就简单了想必大家都理解而他是要交换整棵树因此我们交换完根节点后还要交换他左子树的结点和右子树的结点因此我们可以利用递归传入根的左右结点再继续往下找左右结点进行交换。 完整代码
class Solution {public TreeNode invertTree(TreeNode root) {if(root null){return root;}TreeNode tmp root.left;root.left root.right;root.right tmp;invertTree(root.left);invertTree(root.right);return root;}
}
4、平衡二叉树
习题链接https://leetcode.cn/problems/balanced-binary-tree/description/https://leetcode.cn/problems/balanced-binary-tree/description/
描述给定一个二叉树判断它是否是 平衡二叉树 解题思路 首先我们要先来了解什么是平衡二叉树所谓平衡二叉树就是一个根节点左边的长度和右边的长度的差值要小于等于1. 而根据对平衡二叉树的了解我们发现我们应该去求他左子树和右子树的长度让他们相减。 关于二叉树长度的计算我们再二叉树中已经进行了讲解大家可以去看看。数据结构二叉树 因为我们要判断整棵树是否为平衡二叉树因此我们要从根结点判断是否为平衡二叉树还要对子树的子树进行平衡二叉树的判断如果都是平衡二叉树我们就认为他是平衡二叉树对于这样的判断我们就要用到递归的方式来进行了。 因此我们获得根结点的左右子树长度进行相减并且利用递归传入根的左结点和右结点进行子树的子树判断 完整代码
class Solution {public boolean isBalanced(TreeNode root) {if(root null){return true;}int leftMax getH(root.left);int rightMax getH(root.right);return Math.abs(leftMax - rightMax) 1 isBalanced(root.left) isBalanced(root.right);}public int getH(TreeNode root){if(root null){return 0;}int leftH getH(root.left);int rightH getH(root.right);return Math.max(leftH,rightH)1;}
} 5、对称二叉树
习题链接https://leetcode.cn/problems/symmetric-tree/description/https://leetcode.cn/problems/symmetric-tree/description/
描述给你一个二叉树的根节点 root 检查它是否轴对称。 解题思路 这道题其实和我们第1题是相同的我们还是判断是否相同只是从两棵树的判断到了一棵树左右子树的判断当时我们要注意因为他要判断是否为镜像因此我们判断是否相同是要判断一棵子树的左边和另一棵子树的右边一棵子树的右边和另一棵子树的左边是否结构相同内容相同 完整代码
class Solution {public boolean isSymmetric(TreeNode root) {if(root null){return true;}return isSameTree(root.left,root.right);}public boolean isSameTree(TreeNode p ,TreeNode q){if(p ! null q null || p null q ! null ){return false;}if(p null q null){return true;}if(p.val ! q.val){return false;}return isSameTree(p.left,q.right) isSameTree(p.right,q.left);}
} 6、二叉树遍历
习题链接https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId60tqId29483rp1ru/activity/ojqru/ta/tsing-kaoyan/question-rankinghttps://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId60tqId29483rp1ru/activity/ojqru/ta/tsing-kaoyan/question-ranking 描述
编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。
输入描述
输入包括1行字符串长度不超过100。
输出描述
可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。 解题思路 根据题意我们知道他是要我们根据先序遍历建立一棵二叉树再输出二叉树的中序遍历。 首先我们要根据先序遍历创建二叉树在创建二叉树前我们要创建结点因为二叉树是由一个个结点形成的。 创建完结点后我们就要创建二叉树我们知道先序遍历的顺序是根左右因此我们要先创建完左子树再创建右子树那么什么时候我们停止创建左子树呢 停止的时刻其实是当我们遇到空树的时候而先序遍历给我们的空树就是“#”因此只要我们没遇到“#”就创建左子树并让先序遍历往下走遇到“#”了我们就停止但依然让先序遍历往下走并返回到上面一层去创建右子树。 当右子树也遇到“#”了我们就停止创建二叉树但依然让先序遍历往下走并返回到上面一层此时左右子树都走完了再返回上一层去创建右子树在这样不断的递归和返回就成功创建了二叉树。 当我们创建完二叉树后接下来就是用中序遍历去打印了左根右 完整代码
import java.util.Scanner;
class TreeNode{char val;TreeNode left;TreeNode right;public TreeNode(char val){this.val val;}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static int i 0;public static TreeNode createTree(String str){TreeNode root null;if(str.charAt(i) ! #){root new TreeNode(str.charAt(i));i;root.left createTree(str);root.right createTree(str);}else{i;}return root;}public static void oread(TreeNode root){if(root null){return;}oread(root.left);System.out.print(root.val );oread(root.right);}public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str in.nextLine(); TreeNode root createTree(str);oread(root);}}
}
7、二叉树的分层遍历 习题链接https://leetcode.cn/problems/binary-tree-level-order-traversal/description/https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
描述
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 解题思路 这道题就是让我将二叉树由层序遍历输出而层序遍历的方式我们再上一篇二叉树是已经进行了讲解大家可以去看看数据结构二叉树 而这道虽然仍是以层序遍历输出但是他输出要求是同一层的放到一起输出。 因此我们可以在层序遍历的基础上再创建一个链表curList然后再计算次数队列的长度根据长度决定出队的个数并让出队的元素放到链表curList中并将此时出队的元素左右结点放入队列中当这个循环结束了就代表上一个队列为空了再将curList的值放入到list链表中然后利用循环再判断此时的队列再创建一个新的curList重复上面的操作这样就实现了同一层的放到一起输出 完整代码
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger list new ArrayList();if(root null){return list;}QueueTreeNode q new LinkedList();q.offer(root);while(!q.isEmpty()){ListInteger curList new ArrayList();int size q.size();while(size ! 0){TreeNode cur q.poll();curList.add(cur.val);if(cur.left ! null){q.offer(cur.left);}if(cur.right ! null){q.offer(cur.right);}size--;}list.add(curList); }return list;}
} 好了。今天的分享就到这里了还请大家多多关注我们下一篇再见
