102.二叉树的层序遍历
/**
* 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>> res = new ArrayList<List<Integer>>();//List是接口 无法实例化 因此只能实例化ArrayList
if(root == null) return res;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//用来存放待弹出的节点
queue.offer(root);
while(!queue.isEmpty()){
ArrayList<Integer> resLine = new ArrayList<Integer>();//存放每一行的结果
int len = queue.size();
for(int i=0;i < len;i++){
TreeNode node = queue.poll();
resLine.add(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
res.add(resLine);
}
return res;
}
}
226.翻转二叉树
这道题目二刷，但是还是没有一次通过，出现了输出和输入完全一样的问题，先附上错误代码，而后会以图的形式对比分析错误原因：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
swap(root.left,root.right);
invertTree(root.left);
invertTree(root.right);
return root;
}
public void swap(TreeNode right,TreeNode left){
TreeNode tempNode = right;
right = left;
left = tempNode;
}
}
后面参考了答案，改写了swap方法，通过：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
swap(root);
invertTree(root.left);
invertTree(root.right);
return root;
}
public void swap(TreeNode node){
TreeNode tempNode = node.left;
node.left = node.right;
node.right = tempNode;
}
}
swap方法中，一个是将待翻转节点的左右节点分别传入，一个是直接将待翻转节点传入。这两者有什么区别呢？为什么前者错了？
这其实是和方法传参的机制有关，我们都知道在Java中，对象是通过引用传递的。当你将一个对象作为参数传递给方法时，实际上是传递了一个指向该对象的引用的副本。
那么第一个swap方法其实是分别创建了right和left的副本传入方法中进行交换
进入方法，创建一个tempNode引用指向right（副本）指向的实例对象
然后right（副本）引用指向left（副本）指向的实例对象
最后，left(副本)指向tempNode指向的实例对象
我们可以看出，这个方法只能将left和right指针的副本进行互换，不能对本身的right和left指针互换。
而第二个swap之所以正确，是因为直接将node的副本引用传入方法中
经过交换操作，最终完成了left和right位置的真正互换。
层序遍历
一定要记住最开始要判断root==null的情况
/**
* 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>> res = new ArrayList<List<Integer>>();//List是接口 无法实例化 因此只能实例化ArrayList
if(root == null) return res;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//用来存放待弹出的节点
queue.offer(root);
while(!queue.isEmpty()){
ArrayList<Integer> resLine = new ArrayList<Integer>();//存放每一行的结果
int len = queue.size();
for(int i=0;i < len;i++){
TreeNode node = queue.poll();
resLine.add(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
res.add(resLine);
}
return res;
}
}
对称二叉树
这道题没啥好说的 直接看卡哥视频 非常清晰
只总结一句话：每一个节点需要知道自己的左右节点是否对称才可以判断以自己为根节点的子树是都对称，从叶子节点向上不断返回左右节点对称判定结果的与，最终返回到根节点，得到最终结果。
/**
* 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 false;
return judge(root.right,root.left);
}
public boolean judge(TreeNode right,TreeNode left){
if(right==null && left==null) return true;
else if(right==null && left!=null) return false;
else if(right!=null && left==null) return false;
else if(right.val != left.val) return false;
boolean out = judge(right.right,left.left);
boolean in = judge(right.left,left.right);
return out && in;
}
}
