剑指offer32Ⅰ：从上到下打印二叉树-蒲公英云

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

清疚 2024-02-28 06:42 165阅读 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。全部打印完成结束。

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

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

代码

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，得到所有按照层次组织的节点，这样就是从上到下，从左到右打印二叉树节点。

深度优先搜索

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;
        }
    }
}