基础算法，二叉树的层序遍历！
层次遍历：用于一层一层地访问二叉树中的所有结点。其过程如下：
若二叉树非空（假设其高度为h），则：
（1）访问根节点（第一层）；
（2）从左到右访问第二层的所有结点；
（3）从左到右访问第三层的所有结点，······，第h层的所有结点。
对于层次遍历，先访问结点的左右孩子也要先访问，这样与队列的特征相吻合，因此层次遍历算法可采用一个队列来实现。
层次遍历的具体过程是先将根结点进队，在队列不为空的时候循环，从队列中出列一个结点node，访问它；若它有左孩子结点，将左孩子结点进队；若它有右孩子结点，将右孩子结点进队。如此操作，直到队列为空为止。
leetcode102 二叉树的层序遍历
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
1.BFS，即使用队列的解法如下：
public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> resList = new LinkedList<>();if (root == null) return resList;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> list = new LinkedList<>();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}resList.add(list);}return resList;}
2.此外也可使用DFS，此解法不是本文重点，递归解法如下：
public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> resList = new LinkedList<>();if (root == null) return resList;dfs(root, 1, resList);return resList;}public void dfs(TreeNode root, int len, List<List<Integer>> resList) {if (len > resList.size()) {List<Integer> list = new LinkedList<>();list.add(root.val);resList.add(list);}else {resList.get(len - 1).add(root.val);}if (root.left != null) {dfs(root.left, len + 1, resList);}if (root.right != null) {dfs(root.right, len + 1, resList);}}
学会层次遍历的非递归解法，我们可以轻松解决如下问题，这里列举10道
1.leetcode104 二叉树的最大深度
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
public int maxDepth(TreeNode root) {if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int res = 0;while (!queue.isEmpty()) {int num = queue.size();for (int i = 0; i < num; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}res++;}return res;}
2.leetcode111 二叉树的最小深度
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
public int minDepth(TreeNode root) {if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int res = 0;while (!queue.isEmpty()) {int size = queue.size();res++;for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left == null && node.right == null) {return res;}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return res;}
3.leetcode100 相同的树
https://leetcode-cn.com/problems/same-tree/
public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) return true;if (p == null) return false;if (q == null) return false;Queue<TreeNode> pQueue = new LinkedList<>();Queue<TreeNode> qQueue = new LinkedList<>();pQueue.offer(p);qQueue.offer(q);while (!pQueue.isEmpty() && !qQueue.isEmpty()) {TreeNode pNode = pQueue.poll();TreeNode qNode = qQueue.poll();if (pNode.val != qNode.val) {return false;}if (pNode.left != null && qNode.left != null) {pQueue.offer(pNode.left);qQueue.offer(qNode.left);}else if (pNode.left != null || qNode.left != null) {return false;}if (pNode.right != null && qNode.right != null) {pQueue.offer(pNode.right);qQueue.offer(qNode.right);}else if (pNode.right != null || qNode.right != null) {return false;}}return pQueue.isEmpty() && qQueue.isEmpty();}
4.leetcode101 对称二叉树
https://leetcode-cn.com/problems/symmetric-tree
public boolean isSymmetric(TreeNode root) {if (root == null) return false;return isSym(root.left, root.right);}public boolean isSym(TreeNode rootA, TreeNode rootB){if (rootA == null && rootB == null) return true;if (rootA == null) return false;if (rootB == null) return false;Queue<TreeNode> queueA = new LinkedList<>();Queue<TreeNode> queueB = new LinkedList<>();queueA.offer(rootA);queueB.offer(rootB);while (!queueA.isEmpty() && !queueB.isEmpty()) {TreeNode nodeA = queueA.poll();TreeNode nodeB = queueB.poll();if (nodeA.val != nodeB.val) {return false;}if (nodeA.left != null && nodeB.right != null) {queueA.offer(nodeA.left);queueB.offer(nodeB.right);}else if (nodeA.left != null || nodeB.right != null) {return false;}if (nodeA.right != null && nodeB.left != null) {queueA.offer(nodeA.right);queueB.offer(nodeB.left);}else if (nodeA.right != null || nodeB.left != null) {return false;}}return queueA.isEmpty() && queueB.isEmpty();}
4.leetcode226 翻转二叉树
https://leetcode-cn.com/problems/invert-binary-tree/
public TreeNode invertTree(TreeNode root) {if (root == null) return null;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();TreeNode temp = node.left;node.left = node.right;node.right = temp;if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}return root;}
5.leetcode103 二叉树的锯齿形层序遍历
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> resList = new LinkedList<>();if (root == null) return resList;Deque<TreeNode> deque = new LinkedList<>();deque.add(root);boolean flag = true;while (!deque.isEmpty()) {int size = deque.size();List<Integer> list = new LinkedList<>();for (int i = 0; i < size; i++) {TreeNode node = deque.poll();if (flag) {list.add(node.val);}else {list.add(0, node.val);}if (node.left != null) {deque.offer(node.left);}if (node.right != null) {deque.offer(node.right);}}flag = !flag;resList.add(list);}return resList;}
6.leetcode112 路径总和
https://leetcode-cn.com/problems/path-sum/
public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) return false;Queue<TreeNode> queue = new LinkedList<>();Queue<Integer> tarQueue = new LinkedList<>();queue.offer(root);tarQueue.offer(targetSum - root.val);while (!queue.isEmpty()) {TreeNode node = queue.poll();int target = tarQueue.poll();if (node.left == null && node.right == null && target == 0) {return true;}if (node.left != null) {queue.offer(node.left);tarQueue.offer(target - node.left.val);}if (node.right != null) {queue.offer(node.right);tarQueue.offer(target - node.right.val);}}return false;}
7.leetcode199 二叉树的右视图
https://leetcode-cn.com/problems/binary-tree-right-side-view/
public List<Integer> rightSideView(TreeNode root) {List<Integer> list = new LinkedList();if (root == null) return list;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (i == size - 1) {list.add(node.val);}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return list;}
8.leetcode107 二叉树的层序遍历2
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> resList = new LinkedList<>();if (root == null) return resList;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> list = new LinkedList<>();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}resList.add(0, list);}return resList;}
9.leetcode129 求根到叶子节点数字之和
https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
public int sumNumbers(TreeNode root) {if (root == null) return 0;Queue<TreeNode> queueA = new LinkedList<>();Queue<Integer> queueB = new LinkedList<>();queueA.offer(root);queueB.offer(root.val);int res = 0;while (!queueA.isEmpty()) {TreeNode node = queueA.poll();int value = queueB.poll();if (node.left == null && node.right == null) {res += value;continue;}if (node.left != null) {queueA.offer(node.left);queueB.offer(value * 10 + node.left.val);}if (node.right != null) {queueA.offer(node.right);queueB.offer(value * 10 + node.right.val);}}return res;}
10.leetcode637 二叉树的层平均值
https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
public List<Double> averageOfLevels(TreeNode root) {List<Double> list = new LinkedList<>();Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();double sum = 0;for (int i = 0; i < size; i++) {TreeNode node = queue.poll();sum += node.val;if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}list.add(sum / size);}return list;}
万变不离其宗，会了一种解法，一类问题都将迎刃而解！
写在最后，一点与其他的事。
姐姐离职了，走了，往后无论还是生活还是工作，大概都不会再有交集了吧。其实我的心是很痛的，但我还是会装作若无其事，这是一个男人该有的姿态。早在18岁的时候，我就觉得自己理解了一句话，爱了，让她自由，不爱，让爱自由。如今我22岁，四年过去了，等到自己去经历这句话的时候，我发现要完完全全地做到这句话真的是太难太难了，心碎的滋味真的很难受。
结束了，一切没有变得更好或者更坏，只是回到了它本来的样子。那些所经历的或许终将随着时间的流逝而逐渐变淡，姐姐的容颜也会逐渐地我的脑海里变得模糊。多年之后再回首此事，又会是怎样一番滋味呢？
不管你信不信，人确实是在经历了一些事之后，就悄悄换了一种性格。因为，我就是其中一个，仅一夜之间，我的心就判若两人。我站在人生阅历的风口，吹掉了一生纯真。以前我一杯可乐就能开心好久，如今要喝十瓶啤酒，是成长还是堕落，傻傻分不清楚，有很多人叫我戒烟，却没人问过我，为什么抽烟，你知道我在说什么吗。现在翻翻以前的说说，好像在读另一个自己，不知从什么时候开始，我变得连自己都觉得陌生。好像没有了特别喜欢的人，也没有了特别讨厌的人，更没有了特别要好的朋友。就连喜欢听歌都不是因为谁唱的多好听了，而是因为歌词，写的好像自己。