二叉树（下）
目录
判断树是否相同
判断树是不是另一棵树的子树
二叉树翻转
判断平衡二叉树
二叉树层序遍历
这篇主要提供一些关于二叉树例题的讲解，如果对二叉树及其基本操作有疑问的可以转至：
二叉树（上）-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;
}
Queue<TreeNode> 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 List<List<Integer>> levelOrder2(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if (root == null) {
return ret;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> 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;
}