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

---

comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9832%20-%20I.%20%E4%BB%8E%E4%B8%8A%E5%88%B0%E4%B8%8B%E6%89%93%E5%8D%B0%E4%BA%8C%E5%8F%89%E6%A0%91/README.md

  面试题 32 - I. 从上到下打印二叉树

题目描述

  从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的次序打印。
 
例如:
给定二叉树: [3,9,20,null,null,15,7],

1.     3
2.    / \
3.   9  20
4.     /  \
5.    15   7

复制代码

返回：

1. [3,9,20,15,7]

复制代码

 
提示：

• 节点总数 <= 1000
  

  解法

  方法一：BFS

我们可以通过 BFS 遍历二叉树，将每一层的节点值存入数组中，最后返回数组即可。
时间复杂度                                    O                         (                         n                         )                              O(n)                  O(n)，空间复杂度                                    O                         (                         n                         )                              O(n)                  O(n)。其中                                    n                              n                  n 为二叉树的节点数。
  Python3

1. # Definition for a binary tree node.
2. # class TreeNode:
3. #     def __init__(self, x):
4. #         self.val = x
5. #         self.left = None
6. #         self.right = None
9. class Solution:
10.     def levelOrder(self, root: TreeNode) -> List[int]:
11.         ans = []
12.         if root is None:
13.             return ans
14.         q = deque([root])
15.         while q:#保证层序下去
16.             for _ in range(len(q)):
17.                 node = q.popleft()
18.                 ans.append(node.val)
19.                 if node.left:
20.                     q.append(node.left)
21.                 if node.right:
22.                     q.append(node.right)
23.         return ans

复制代码

Java

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[] {};
14.         }
15.         Deque<TreeNode> q = new ArrayDeque<>();
16.         q.offer(root);
17.         List<Integer> res = new ArrayList<>();
18.         while (!q.isEmpty()) {
19.             for (int n = q.size(); n > 0; --n) {
20.                 TreeNode node = q.poll();
21.                 res.add(node.val);
22.                 if (node.left != null) {
23.                     q.offer(node.left);
24.                 }
25.                 if (node.right != null) {
26.                     q.offer(node.right);
27.                 }
28.             }
29.         }
30.         int[] ans = new int[res.size()];
31.         for (int i = 0; i < ans.length; ++i) {
32.             ans[i] = res.get(i);
33.         }
34.         return ans;
35.     }
36. }

复制代码

C++

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8. * };
9. */
10. class Solution {
11. public:
12.     vector<int> levelOrder(TreeNode* root) {
13.         if (!root) {
14.             return {};
15.         }
16.         vector<int> ans;
17.         queue<TreeNode*> q{{root}};
18.         while (!q.empty()) {
19.             for (int n = q.size(); n; --n) {
20.                 auto node = q.front();
21.                 q.pop();
22.                 ans.push_back(node->val);
23.                 if (node->left) {
24.                     q.push(node->left);
25.                 }
26.                 if (node->right) {
27.                     q.push(node->right);
28.                 }
29.             }
30.         }
31.         return ans;
32.     }
33. };

复制代码

Go

1. /**
2. * Definition for a binary tree node.
3. * type TreeNode struct {
4. *     Val int
5. *     Left *TreeNode
6. *     Right *TreeNode
7. * }
8. */
9. func levelOrder(root *TreeNode) (ans []int) {
10.         if root == nil {
11.                 return
12.         }
13.         q := []*TreeNode{root}
14.         for len(q) > 0 {
15.                 for n := len(q); n > 0; n-- {
16.                         node := q[0]
17.                         q = q[1:]
18.                         ans = append(ans, node.Val)
19.                         if node.Left != nil {
20.                                 q = append(q, node.Left)
21.                         }
22.                         if node.Right != nil {
23.                                 q = append(q, node.Right)
24.                         }
25.                 }
26.         }
27.         return
28. }

复制代码

TypeScript

1. /**
2. * Definition for a binary tree node.
3. * class TreeNode {
4. *     val: number
5. *     left: TreeNode | null
6. *     right: TreeNode | null
7. *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8. *         this.val = (val===undefined ? 0 : val)
9. *         this.left = (left===undefined ? null : left)
10. *         this.right = (right===undefined ? null : right)
11. *     }
12. * }
13. */
15. function levelOrder(root: TreeNode | null): number[] {
16.     const ans: number[] = [];
17.     if (!root) {
18.         return ans;
19.     }
20.     const q: TreeNode[] = [root];
21.     while (q.length) {
22.         const t: TreeNode[] = [];
23.         for (const { val, left, right } of q) {
24.             ans.push(val);
25.             left && t.push(left);
26.             right && t.push(right);
27.         }
28.         q.splice(0, q.length, ...t);
29.     }
30.     return ans;
31. }

复制代码

Rust

1. // Definition for a binary tree node.
2. // #[derive(Debug, PartialEq, Eq)]
3. // pub struct TreeNode {
4. //   pub val: i32,
5. //   pub left: Option<Rc<RefCell<TreeNode>>>,
6. //   pub right: Option<Rc<RefCell<TreeNode>>>,
7. // }
8. //
9. // impl TreeNode {
10. //   #[inline]
11. //   pub fn new(val: i32) -> Self {
12. //     TreeNode {
13. //       val,
14. //       left: None,
15. //       right: None
16. //     }
17. //   }
18. // }
19. use std::cell::RefCell;
20. use std::collections::VecDeque;
21. use std::rc::Rc;
22. impl Solution {
23.     pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
24.         let mut ans = Vec::new();
25.         let mut q = VecDeque::new();
26.         if let Some(node) = root {
27.             q.push_back(node);
28.         }
29.         while let Some(node) = q.pop_front() {
30.             let mut node = node.borrow_mut();
31.             ans.push(node.val);
32.             if let Some(l) = node.left.take() {
33.                 q.push_back(l);
34.             }
35.             if let Some(r) = node.right.take() {
36.                 q.push_back(r);
37.             }
38.         }
39.         ans
40.     }
41. }

复制代码

JavaScript

1. /**
2. * Definition for a binary tree node.
3. * function TreeNode(val) {
4. *     this.val = val;
5. *     this.left = this.right = null;
6. * }
7. */
8. /**
9. * @param {TreeNode} root
10. * @return {number[]}
11. */
12. var levelOrder = function (root) {
13.     const ans = [];
14.     if (!root) {
15.         return ans;
16.     }
17.     const q = [root];
18.     while (q.length) {
19.         const t = [];
20.         for (const { val, left, right } of q) {
21.             ans.push(val);
22.             left && t.push(left);
23.             right && t.push(right);
24.         }
25.         q.splice(0, q.length, ...t);
26.     }
27.     return ans;
28. };

复制代码

C#

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     public int val;
5. *     public TreeNode left;
6. *     public TreeNode right;
7. *     public TreeNode(int x) { val = x; }
8. * }
9. */
10. public class Solution {
11.     public int[] LevelOrder(TreeNode root) {
12.         if (root == null) {
13.             return new int[]{};
14.         }
15.         Queue<TreeNode> q = new Queue<TreeNode>();
16.         q.Enqueue(root);
17.         List<int> ans = new List<int>();
18.         while (q.Count != 0) {
19.             int x = q.Count;
20.             for (int i = 0; i < x; i++) {
21.                 TreeNode node = q.Dequeue();
22.                 ans.Add(node.val);
23.                 if (node.left != null) {
24.                     q.Enqueue(node.left);
25.                 }
26.                 if (node.right != null) {
27.                     q.Enqueue(node.right);
28.                 }
29.             }
30.         }
31.         return ans.ToArray();
32.     }
33. }

复制代码

Swift

1. /* public class TreeNode {
2. *     var val: Int
3. *     var left: TreeNode?
4. *     var right: TreeNode?
5. *     init(_ val: Int) {
6. *         self.val = val
7. *         self.left = nil
8. *         self.right = nil
9. *     }
10. * }
11. */
13. class Solution {
14.     func levelOrder(_ root: TreeNode?) -> [Int] {
15.         guard let root = root else {
16.             return []
17.         }
19.         var queue: [TreeNode] = [root]
20.         var result: [Int] = []
22.         while !queue.isEmpty {
23.             let node = queue.removeFirst()
24.             result.append(node.val)
26.             if let left = node.left {
27.                 queue.append(left)
28.             }
29.             if let right = node.right {
30.                 queue.append(right)
31.             }
32.         }
34.         return result
35.     }
36. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。