1. LeetCode 102. 二叉树的层序遍历
1.1 思路
- 二叉树的层序遍历就相当于图论里的广度优先搜索，之前的递归遍历就相当于图论里的深度优先搜索
- 只依赖二叉树的结构本身是无法做到层序遍历的，因此需要借助一个队列的数据结构
- 首先将根节点放入，每一层要记录当时队列的长度，这个长度就相当于这层有几个元素，然后根据这个长度把每一层的元素弹出放入一个集合中，因为层序遍历返回的是List<List<Integer>>，就相当于一个二维数组，每一层就是每一维，如果没有这个长度记录那么队列既有这一层又有下一层时就混乱了
- 在弹出元素时再判断这个元素是否有左右孩子，有就放入队列，在原本层里的元素都弹出后再记录新的长度，每弹出一个元素长度就--
1.2 代码
class Solution { public List<List<Integer>> list=new ArrayList<>(); public List<List<Integer>> levelOrder(TreeNode root) { func(root); return list; } public void func(TreeNode node){ if(node==null)return; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(node); int len=queue.size(); List<Integer> tempList; TreeNode tempNode; while(!queue.isEmpty()){ tempList=new ArrayList<>(); len=queue.size(); while(len-->0){ tempNode=queue.poll(); tempList.add(tempNode.val); if(tempNode.left!=null)queue.offer(tempNode.left); if(tempNode.right!=null)queue.offer(tempNode.right); } list.add(tempList); } } }
2. LeetCode 226. 翻转二叉树
2.1 思路
- 应该用什么遍历方式？递归还是非递归？递归的话是前中后序？要把这些想清楚
- 前序和后序是最方便的，中序也可以但很麻烦
- 确定递归的参数和返回值：返回值TreeNode，参数TreeNode 根节点
- 终止条件：遇到空节点了，if(root==null)return root;
- 处理逻辑：以前序遍历为例，前序遍历是“根左右”，那么交换就是swap(root.left,root.right)，然后递归调用函数，分别是invertTree(root.left),invertTree(root.right)
- 如果是后序遍历，那么就把swap写在左右子树的下面即可
- 为什么中序不可以呢？其实如果是把swap写在中间的话，那么先把左子树翻转了，再把左右子树swap，那么此时的左子树就是原来的右子树，但接下来是invertTree(root.right)，就相当于又处理原来的左子树了，即原来的右子树就没有处理，所以我们把invertTree(root.right)改为invertTree(root.left)即可
2.2 代码
class Solution { /** * 前后序遍历都可以 * 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换） */ public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } invertTree(root.left); invertTree(root.right); swapChildren(root); return root; } private void swapChildren(TreeNode root) { TreeNode tmp = root.left; root.left = root.right; root.right = tmp; } }
3. LeetCode 101. 对称二叉树
3.1 思路
- 二叉树类的题目确定遍历顺序是很重要的，这题我们用递归的方式，应该用前中后哪个呢？这题只能用后序，后序是“左右根”，因为我们要不断收集左右孩子的信息返回给上一个（即父节点）节点，再收集左右孩子的信息返回给上一个节点，这样才能知道以这个左节点为根节点的树和右节点为根节点的树是否是可以相互翻转的。因为只有后续遍历，才能知道把底部的孩子的信息是否相等的信息返回给上一层
- 确认递归的参数和返回值：由于上述所说，是否是对称二叉树就是判断左右子树是否是可以翻转的，因此定义一个函数，传入左子树和右子树，返回值就是是否是可以翻转的
- 终止条件：如果左节点为空右节点不为空，就是不可翻转的就return false；如果左节点不为空右节点为空，同理return false；如果左右都为空就是可翻转的return true；如果左右都不为空但值不相等，就return false；如果左右节点不为空且值相等就继续向下遍历
- 处理单层递归的逻辑：因为我们要比较外侧节点和内侧节点，如果相同就为true。于是递归调用函数boolean outside= compare(left.left , right.right)，这就是左孩子的左孩子和右孩子的右孩子，即外侧节点的比较；然后再比较内侧节点，boolean inside=compare(left.right , right.left)，这就是左孩子的右孩子和右孩子的左孩子，即内侧节点
- 最后是用布尔值result=outside&&inside，同时外侧和内侧相同，这才说明是对称的，最后return result
3.2 代码
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; } }
