【leetcode】平衡二叉树、对称二叉树、二叉树的层序遍历(广度优先遍历）（详解）

Hi~！这里是奋斗的明志，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
🌱🌱个人主页：奋斗的明志
🌱🌱所属专栏：数据结构、LeetCode专栏

在这里插入图片描述

📚本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

在这里插入图片描述

二叉树面试题

一、平衡二叉树
- 1. 题目
- 2. 解析
- 3. 完整代码
- 4.总结
二、对称二叉树
- 1. 题目
- 2. 解析
- 3. 完整代码(递归的思想)
- 4.迭代实现
三、二叉树的层序遍历
- 1.题目
- 2.解析（利用广度优先搜索）
- 3.完整代码
四、总结

一、平衡二叉树

110.平衡二叉树

1. 题目

在这里插入图片描述

2. 解析

什么是平衡二叉树？

在本题中，平衡二叉树是指该树所有节点的左右子树的深度相差不超过 1。

在这里插入图片描述

①：如果这棵树为空，呢么判断它是平衡二叉树

// 如果是一颗空树
if (root == null) {return true;
}

②：计算根节点左右两边的左子树、右子树的高度。前面写过计算树的高度.
③：在求一棵树的高度时，如果数为空，则返回0，树的高度为0

// 首先判断是否为空树
if (root == null) {return 0;
}

④：如果左子树的高度小于0，表示左子树不平衡，直接返回-1。如果左子树平衡，则继续获取右子树的高度。

// 代码走到这，说明该树不为空，可能只有根节点，可能有多个子树int leftHeight = getHeight(root.left);if (leftHeight < 0) {return -1;}int rightHeight = getHeight(root.right);

⑤：如果左右子树都平衡且它们的高度差不超过1，则当前树也是平衡的，返回当前树的高度（左右子树中较大高度加1）。如果不满足上述条件，说明当前树不平衡，返回-1。

// 刚刚已经约定，不平衡会返回负数if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {return Math.max(leftHeight, rightHeight) + 1;} else {// 不平衡return -1;}

⑥：时间复杂度为 O(N)

3. 完整代码

/*** 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 boolean isBalanced(TreeNode root) {// 如果是一颗空树if (root == null) {return true;}int leftH = getHeight(root.left);int rightH = getHeight(root.right);return getHeight(root) >= 0;}// 求一颗数的高度public int getHeight(TreeNode root) {// 首先判断是否为空树if (root == null) {return 0;}// 代码走到这，说明该树不为空，可能只有根节点，可能有多个子树int leftHeight = getHeight(root.left);if (leftHeight < 0) {return -1;}int rightHeight = getHeight(root.right);// 刚刚已经约定，不平衡会返回负数if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {return Math.max(leftHeight, rightHeight) + 1;} else {// 不平衡return -1;}}
}

4.总结

在遍历每个结点进行左右子树求高度的时候，就进行判断，能够优化时间复杂度
该题有递归的思想，一定要结合图形来解决

二、对称二叉树

101.对称二叉树

1. 题目

在这里插入图片描述

2. 解析

在这里插入图片描述
①：从图中可以看出当该树为空时，判断该树也是对称二叉树
②：当该树不为空的时候，判断左右子树是否对称

③：看 lt 的左子树是否和 rt 的右子树是否对称
④：看 lt 的右子树是否和 rt 的左子树是否对称

3. 完整代码(递归的思想)

/*** 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 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) || (leftTree != null && rightTree == null)) {return false;}if (leftTree == null && rightTree == null) {return true;}if (leftTree.val != rightTree.val) {return false;}return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);}
}

4.迭代实现

在这里插入图片描述

class Solution {public boolean isSymmetric(TreeNode root) {return check(root, root);}public boolean check(TreeNode u, TreeNode v) {Queue<TreeNode> q = new LinkedList<TreeNode>();q.offer(u);q.offer(v);while (!q.isEmpty()) {u = q.poll();v = q.poll();if (u == null && v == null) {continue;}if ((u == null || v == null) || (u.val != v.val)) {return false;}q.offer(u.left);q.offer(v.right);q.offer(u.right);q.offer(v.left);}return true;}
}

三、二叉树的层序遍历

102.二叉树的层序遍历

1.题目

在这里插入图片描述

2.解析（利用广度优先搜索）

在这里插入图片描述

外层循环 (while (!queue.isEmpty()))：只要队列不为空，就继续进行层序遍历。
内层循环：处理当前队列中的所有节点，这些节点是当前层的节点。
queueSize 记录当前层的节点个数，初始化为队列的大小。
list 用来存储当前层的节点值。
while (queueSize != 0) 循环处理当前层的所有节点：
从队列中取出节点 cur，并将其值 cur.val 添加到 list 中。
将 cur 的左右子节点（如果存在）依次加入队列中，以便处理下一层。
层结束：内层循环结束后，表示当前层的所有节点已经处理完毕，将 list 添加到 retList 中，表示当前层的节点值已经记录完毕。

3.完整代码

/*** 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 List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> retList = new ArrayList<>();// 如果为空树，直接返回 空的二维数组if (root == null) {return retList;}// 利用队列来辅助实现Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);// 首先将根节点添加到队列while (!queue.isEmpty()) {// 计算当前队列里面的个数int queueSize = queue.size();List<Integer> list = new ArrayList<>();while (queueSize != 0) {// 出队列一个结点，并添加到数组当中TreeNode cur = queue.poll();list.add(cur.val);// 出队列之后 有效个数减一queueSize--;// 然后向队列里面添加这个根节点的孩子结点// 对孩子节点进行判断if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}}retList.add(list);}return retList;}
}