剑指offer32Ⅰ：从上到下打印二叉树

清疚 2024-02-28 06:42 50阅读 0赞

### 题目描述 ###

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

> 给定二叉树: \[3,9,20,null,null,15,7\],
> 
> 3  
> / \\  
> 9 20  
> / \\  
> 15 7  
>   
> 返回其层次遍历结果：
> 
> \[3,9,20,15,7\]

提示：

节点总数 <= 1000

### 思路 ###

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

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

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

![cff6ab571c3c441ea0e81ac20f594f0b.png][]

### 代码 ###

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;
        }
    
        @Override
        public String toString() {
            return val + "";
        }
    }

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

![231a1e45a55242d78959ed881579b803.png][]

### 深度优先搜索 ###

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\]\]，相信经过上面的深度优先搜索，大家也许有一些想法，这个代码或许简单改造一下就可以了。

[cff6ab571c3c441ea0e81ac20f594f0b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/28/2be4cde9206543d7b590207eb2aeed2b.png
[231a1e45a55242d78959ed881579b803.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/28/002ced00cd5a4bd7bea1bde8385a3600.png