如何建一个企业网站,广州seo技术外包公司,杰商网站建设,北京seo怎么优化目录
判断树是否相同
判断树是不是另一棵树的子树
二叉树翻转
判断平衡二叉树 二叉树层序遍历 这篇主要提供一些关于二叉树例题的讲解#xff0c;如果对二叉树及其基本操作有疑问的可以转至#xff1a;
二叉树#xff08;上#xff09;-CSDN博客二叉树#xff08;中如果对二叉树及其基本操作有疑问的可以转至
二叉树上-CSDN博客二叉树中-CSDN博客
判断树是否相同
力扣链接100. 相同的树 - 力扣LeetCode
题目描述 给你两棵二叉树的根节点 p 和 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);
完整代码为
//时间复杂度 min(p q)
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//1.先判断结构是否相同if(p ! null q null || p null q ! null){return false;}//2.剩下的两种情况为 空或者相等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);}
} 判断树是不是另一棵树的子树
力扣链接572. 另一棵树的子树 - 力扣LeetCode
情况可以大致分为以下三种 思路为 当前子树和根节点是否一样判断子树是不是和当前root的左子树一样判断子树是不是和当前root的右子树一样 这里其实也调用了上面写的 判断树是否相同 的代码
先用 root 和 subRoot(子树) 进行判断树是否相同然后用root的左子树和右子树同subroot进行递归比较分别进行比较和返回。
注意先是比较两棵树是否为子树关系然后进行递归。
//时间复杂度
//root共有节点r个subRoot共有节点s个
//时间复杂度为O(r * s)
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) {//1.先判断结构是否相同if(p ! null q null || p null q ! null){return false;}//2.剩下的两种情况为 空或者相等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);}}
二叉树翻转
力扣链接226. 翻转二叉树 - 力扣LeetCode 主要思路其实和数据的交换位置是一个类型的像是下面的代码部分 TreeNode tmp root.left;root.left root.right;root.right tmp;
然后进行递归同时加上递归条件和特定情况
class Solution {public TreeNode invertTree(TreeNode root) {if(root null){return root;}//避免叶子节点再进行if(root.left null root.right 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如果 2 则不是平衡二叉树。 思路遍历这棵树的节点求每个节点的左树和右树的高度如果发现h 2则返回false。 判断整棵树会发现根节点的左子树为平衡二叉树右子树也是平衡二叉树。 这里可以先尝试把框架搭建出来求左子树的高度和右子树的高度 public boolean isBalanced(TreeNode root) {if(root null){return true;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return Math.abs(leftHeight - rightHeight) 2 isBalanced(root.left) isBalanced(root.right);}
因为要求每棵树的左右树高所以我们需写一个额外的方法来进行。 public int getHeight(TreeNode root){if(root null){return 0;}int leftTree getHeight(root.left);int rightTree getHeight(root.right);return leftTree rightTree ? leftTree 1 : rightTree 1;}
完整代码为
//时间复杂度为O(N^2)
class Solution {public boolean isBalanced(TreeNode root) {if(root null){return true;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return Math.abs(leftHeight - rightHeight) 2 isBalanced(root.left) isBalanced(root.right);}public int getHeight(TreeNode root){if(root null){return 0;}int leftTree getHeight(root.left);int rightTree getHeight(root.right);return leftTree rightTree ? leftTree 1 : rightTree 1;}
} 二叉树层序遍历
力扣链接102. 二叉树的层序遍历 - 力扣LeetCode
第一种方法队列 思路主要是依靠队列来实现层序遍历先把头节点设为cur询问队列时候为空再去除头节点并输出若左右子树不为则分别放入左右子树
public void levelOrder(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);}}
}
第二种方法队列 二维数组
也就是力扣链接里的题目它主要是让我们把每一层的数据放在一起这里我们可以通过定义一个size变量来记录每一层数据的个数。
public ListListInteger levelOrder2(TreeNode root) {ListListInteger ret new ArrayList();if (root null) {return ret;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {int size queue.size();ListInteger list new ArrayList();while (size ! 0) {TreeNode cur queue.poll();list.add(cur.val);//System.out.print(cur.val );if (cur.left ! null) {queue.offer(cur.left);}if (cur.right ! null) {queue.offer(cur.right);}size--;}ret.add(list);}return ret;
}
