二叉树part02
今日内容：
● 层序遍历 10
● 226.翻转二叉树
● 101.对称二叉树
1.层序遍历
- 102.二叉树的层序遍历
- 107.二叉树的层次遍历II
- 199.二叉树的右视图(opens new window)
- 637.二叉树的层平均值(opens new window)
- 429.N叉树的层序遍历(opens new window)
- 515.在每个树行中找最大值(opens new window)
- 116.填充每个节点的下一个右侧节点指针(opens new window)
- 117.填充每个节点的下一个右侧节点指针II(opens new window)
- 104.二叉树的最大深度(opens new window)
- 111.二叉树的最小深度
2.226.翻转二叉树
/**
* 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 TreeNode invertTree(TreeNode root) {
//就是反转完这两棵二叉树是对称的
//那么问题来了，是在原来的二叉树进行改变，还是定义一个新的二叉树作为接收
//看完代码随想录思路：用递归遍历再原有的树上交换左右孩子指针
//当然，这道题用层序遍历也是可以的（这里用到的）
if(root==null){
return null;
}
//定义一个二叉树作为返回
TreeNode result=null;
//定义一个队列
Queue<TreeNode> queue=new LinkedList<>();
//将根节点存进队列中
queue.add(root);
while(!queue.isEmpty()){
//队列不为空
//记录当前队列内存
int size=queue.size();
for(int i=0;i<size;i++){
//栈顶元素进行存储
TreeNode node=queue.peek();
queue.poll();
//进行交换左右孩子
swap(node);
//继续入队列（左右孩子），然后再下一次继续遍历左右孩子交换他们的左右孩子
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
}
return root;//返回原有树，在本来的树上进行操作
}
//定义一个交换函数
public void swap(TreeNode root){
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
}
3. 101.对称二叉树
/**
* 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) {
//就是将沿着根节点，进行对折，节点位置和值都能够完全重合
//看完代码随想录的思路
//利用递归遍历，比较根节点的左右孩子整棵树的内外侧是否完全相等
//内外侧比较的结果返回给父节点
//要注意比较的不是根节点的左右孩子节点，而是比较左右孩子整棵树
return compare(root.left,root.right);//传入左右子节点
}
//确定递归遍历的返回值和参数
public boolean compare(TreeNode left,TreeNode right){
//排除左右节点比较不符合遍历的
if(left==null&&right!=null){
return false;
}else if(left!=null&&right==null){
return false;
}else if(left==null&&right==null){
return true;
}else if(left.val!=right.val){
return false;
}
//接下来就都是根节点的左右节点不为空且值相等的了
//往下进行遍历
//比较外侧节点
boolean outside=compare(left.left,right.right);
//比较内测节点
boolean inside=compare(left.right,right.left);
//将这个内外侧节点并集的结果返回给父节点
boolean result=outside&&inside;
//将这个结果进行返回
return result;
//这道题用到的是后续遍历，左右中
}
}
