剑指offer-- 32 - I. 从上到下打印二叉树

妖狐艹你老母 2023-02-22 08:20 107阅读 0赞

题目描述

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

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

  1. 3

/
9 20
/
15 7

返回:

[3,9,20,15,7]

提示:

节点总数 <= 1000

思路:二叉树的层序遍历BFS

利用队列层序遍历每个节点
动态数组ArrayList动态添加每个节点值
核心:queue中取出一个节点,再将该节点的左右孩子加入队列

解决方法

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. class Solution {
  11. public int[] levelOrder(TreeNode root) {
  12. if(root == null) //空树则返回空数组
  13. return new int[0];
  14. Queue<TreeNode> queue = new LinkedList<>();
  15. ArrayList<Integer> list = new ArrayList<>();
  16. queue.offer(root);
  17. //核心:queue中取出一个节点,再将该节点的左右孩子加入队列
  18. while(queue.size() != 0){
  19. TreeNode node = queue.poll();
  20. list.add(node.val);
  21. if(node.left != null)
  22. queue.offer(node.left);
  23. if(node.right != null)
  24. queue.offer(node.right);
  25. }
  26. //将ArrayList转换为int数组并返回
  27. int[] res = new int[list.size()];
  28. for(int i=0; i<res.length; i++)
  29. res[i] = list.get(i);
  30. return res;
  31. }
  32. }

发表评论

表情:
评论列表 (有 0 条评论,107人围观)

还没有评论,来说两句吧...

相关阅读