网站建设开票分类编码知乎推广合作

    题目描述

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:

给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
      /  \
   15   7
   
返回其层次遍历结果：

[3,9,20,15,7]

提示：

节点总数 <= 1000

   思路

     这个题目的意思很明确，就是从根节点开始，一层一层打印节点，而且节点顺序是从左到右。以上面示例为例，3为根节点，之后打印它的左右节点9，20，之后再打印20的子节点15，7。全部打印完成结束。

   这道题有点类似图算法中的广度优先搜索，先从顶端开始，依次遍历图的下一层节点，下一层节点遍历完成，接着遍历下下一层。仅仅依赖树结构的左右节点关系，然后递归遍历，我们无法得到最终结果，因为随着层数的增加，兄弟节点之间没有必然关系，他们无法保证从左到右来遍历。

    这里我们需要借助一个队列来存放遍历过的节点，这样，每遍历依次，后续的遍历，我们从队列开头取元素，这样就可以保证按照层级和左右顺序来打印树节点。

 代码

package com.xxx.example;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Offer32PrintTreeNode {private static TreeNode root;private static List<List<Integer>> nodeList = new ArrayList<>();public static void main(String[] args) {TreeNode treeNode = new TreeNode(3);TreeNode treeNode1 = new TreeNode(9);TreeNode treeNode2 = new TreeNode(20);TreeNode treeNode3 = new TreeNode(15);TreeNode treeNode4 = new TreeNode(7);root = treeNode;treeNode2.left = treeNode3;treeNode2.right = treeNode4;root.left = treeNode1;root.right = treeNode2;int[] result = levelOrder(root);for(int i=0;i<result.length;i++) {System.out.print(result[i] + " ");}System.out.println();}public static int[] levelOrder(TreeNode root) {if (root == null)return new int[0];Queue<TreeNode> queue = new LinkedList<>();ArrayList<Integer> list = new ArrayList<>();queue.add(root);while (!queue.isEmpty()) {TreeNode curNode = queue.poll();list.add(curNode.val);if (curNode.left != null)queue.add(curNode.left);if (curNode.right != null)queue.add(curNode.right);}return list.stream().mapToInt(Integer::intValue).toArray();}}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int value) {this.val = value;this.left = null;this.right = null;}@Overridepublic String toString() {return val + "";}
}

    还有一种办法，其实就是利用深度优先搜索的思想解决，这个似乎有点玄妙，这里明明是要广度优先搜索，怎么还利用起深度优先搜索呢？其实是这样的，这里按照深度优先搜索，我们只是把搜到的数据打上标签，这个标签就是它的层次，也叫深度，每个深度的节点我们保存到同样深度的map映射里。最后，我们遍历map，得到所有按照层次组织的节点，这样就是从上到下，从左到右打印二叉树节点。 

深度优先搜索 

package com.xxx.tutorial;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TreeNodeTraversal {private static Map<Integer, List<Integer>> map = new HashMap<>();private static int max = -1;private static int cnt = 0;public static void main(String[] args) {TreeNode node0 = new TreeNode(3);TreeNode node1 = new TreeNode(9);TreeNode node2 = new TreeNode(20);TreeNode node3 = new TreeNode(15);TreeNode node4 = new TreeNode(7);node0.left = node1;node0.right = node2;node2.left = node3;node2.right = node4;int[] res = traversal(node0);for (int i = 0; i < res.length; i++) {System.out.print(res[i] + " ");}System.out.println();}public static int[] traversal(TreeNode root) {dfs(root, 0);int[] ans = new int[cnt];for (int i = 0, idx = 0; i <= max; i++) {for (int x : map.get(i))ans[idx++] = x;}return ans;}public static void dfs(TreeNode node, int depth) {if (node == null) return;max = Math.max(max, depth);cnt++;dfs(node.left, depth + 1);List<Integer> list = map.getOrDefault(depth, new ArrayList<>());list.add(node.val);map.put(depth, list);dfs(node.right, depth + 1);}public static class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int value) {this.val = value;this.left = null;this.right = null;}}
}

    这里通过递归调用，我们能遍历完所有节点，并按照深度层次保存各自深度的节点。 

    这个思路很巧妙，它利用深度层次来映射对应的节点，最后，我们遍历map映射得到所有节点，他们的顺序正好是从上到下，从左到右。

    剑指offer打印二叉树还有另一个题目，就是按照层次打印二叉树，就是[[3],[9,20],[15,7]]，相信经过上面的深度优先搜索，大家也许有一些想法，这个代码或许简单改造一下就可以了。