雄安网站建设多少钱,网页微博怎么退出登录,软件工程专业就业前景,营销型网站建设公司排名✅每日一练#xff1a;100. 相同的树 - 力扣#xff08;LeetCode#xff09; 题目的意思是俩棵树的结构不仅要相同#xff0c;而且每个节点的值还要相同#xff0c;如果满足上面2个条件#xff0c;则成立#xff01;
解题思路#xff1a;
从三个方面去考虑#xff1… ✅每日一练100. 相同的树 - 力扣LeetCode 题目的意思是俩棵树的结构不仅要相同而且每个节点的值还要相同如果满足上面2个条件则成立
解题思路
从三个方面去考虑
1.如果p,q都为空那么一定相同
2.如果p为空q不为空或者p不为空q为空那么一定不相同
3.如果二者都不为空那么需要判断根节点如果根节点不相同那么一定不相同如果相同我们需要比较左右子树的值和左右子树的结构
代码
public boolean isSameTree(TreeNode p, TreeNode q) {//如果p,q都为空那么这2个树一定相同if (p null q null) {return true;}//如果q为空p不为空那么一定不相同,或者p为空q不为空那么一定不相同if (p ! null q null||p null q ! null) {return false;}//如果p,q都不为空那么要判断值如果值不相同那么一定不相同if (p.val ! q.val) {return false;}//如果p,q都不为空并且p,q的值相同那么要判断p,q的左右子树的值如果相同为真反之return isSameTree(p.left, q.left) isSameTree(p.right, q.right);} ✅每日一练572. 另一棵树的子树 - 力扣LeetCode 解题思路
1.如果根节点为空那么返回false;
2.如果根节点相同那么我们需要判断这2棵树是否相同我们可以借助上面写的isSameTree方法去判断如果相同则subRoot是root的子树
3.如果根节点不相同我们需要在左子树或者右子树去找是否有和subRoot相同的树
代码
public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root null||subRoot null){return false;}//判断2棵树是否相同if(isSameTree(root,subRoot)){return true;}//判断左子树是否有subRootif(isSubtree(root.left,subRoot)){return true;}//判断右子树是否有subRootif(isSubtree(root.right,subRoot)){return true;}return false;}public boolean isSameTree(TreeNode p, TreeNode q) {//如果p,q都为空那么这2个树一定相同if (p null q null) {return true;}//如果q为空p不为空那么一定不相同if (p ! null q null) {return false;}//如果p为空q不为空那么一定不相同if (p null q ! null) {return false;}//如果p,q都不为空那么要判断值如果值不相同那么一定不相同if (p.val ! q.val) {return false;}//如果p,q都不为空并且p,q的值相同那么要判断p,q的左右子树的值如果相同为真反之return isSameTree(p.left, q.left) isSameTree(p.right, q.right);} ✅每日一练226. 翻转二叉树 - 力扣LeetCode 解题思路
利用递归思想如果根节点不为空递归左右子树的值进行交换
public TreeNode invertTree(TreeNode root) {if (root null) {return null;}TreeNode tmp root.left;root.left root.right;root.right tmp;invertTree(root.left);invertTree(root.right);return root;} ✅每日一练110. 平衡二叉树 - 力扣LeetCode 解题思路
题目的意思就是每个节点的左右子树的高度差的绝对值不能超过1就是平衡二叉树则满足题目需求
代码
public boolean isBalanced(TreeNode root) {if(root null){return true;}int leftH getHeight(root.left);int rightH getHeight(root.right);return Math.abs(leftH-rightH)1 isBalanced(root.left) isBalanced(root.right);}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;} ✅每日一练101. 对称二叉树 - 力扣LeetCode 解题思路
1.如果根节点为空那么对称
2.如果根节点不为空根节点的左子树为空根节点的右子树不为空或者根节点的左子树不为空根节点的右子树为空那么一定不对称
3.如果根节点的左子树的值和右子树的值不相等那么一定不对称
4.如果上面条件都没有满足到那么我们需要判断左子树的左子树是否和右子树的右子树相等左子树的右子树是否和右子树的左子树相等如果相等则对称
代码
public boolean isSymmetric(TreeNode root) {if (root null) {return true;}return isSymmetricChild(root.left, root.right);}public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {if (leftTree null rightTree null) {return true;}if (leftTree ! null rightTree null || leftTree null rightTree ! null) {return false;}if (leftTree.val ! rightTree.val) {return false;}return isSymmetricChild(leftTree.left, rightTree.right) isSymmetricChild(leftTree.right, rightTree.left);} ✅每日一练102. 二叉树的层序遍历 - 力扣LeetCode 解题思路
层序遍历就是从上到下从左到右逐个遍历层序遍历相对于其他遍历简单但是代码实现起来没有那么简单 我们可以利用队列去实现他利用队列先进先出的特点去实现
首先判断根节点如果为空就返回如果不为空就把根节点放进队列用while循环来判断当前队列是否为空再定义一个变量来存放根节点的值然后打印打印完再去判断根节点的左右子树如果不为空就入队依次执行下去我们可以得到层序遍历代码
public void levelOrder1(TreeNode root) {if (root null) {return;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {TreeNode cur queue.poll();System.out.print(cur.val );if (cur.left ! null) {queue.offer(cur.left);}if (cur.right ! null) {queue.offer(cur.right);}}}
这是没有返回值的方法但是这道oj题的返回值是ListListInteger所以这是我们就要换种思路来写这题了大致的思路就是我们需要2的循环用当前队列是否为空作为第一个循环条件当前队列里面元素的个数的大小作为子循环条件代码
public ListListInteger levelOrder(TreeNode root) {ListListInteger list new ArrayList();if (root null) {return list;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {int size queue.size();//用来判断当前队列的大小//System.out.print(cur.val);ListInteger tmp new ArrayList();while (size ! 0) {TreeNode cur queue.poll();tmp.add(cur.val);size--;if (cur.left ! null) {queue.offer(cur.left);}if (cur.right ! null) {queue.offer(cur.right);}}list.add(tmp);//将每层的结果放到list中}return list;}
