时间戳

首页 > 技术文章 > 从上到下打印二叉树，按行打印（Python and C++解法）

从上到下打印二叉树，按行打印（Python and C++解法）

kongzimengzixiaozhuzi 2020-07-08 20:01 原文

题目：

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof

思路：

　　本体实质上是广度优先搜索，自然少不了队列结构做辅助。每一层要打印的节点数量和下一层要打印的节点数量要记录下来。

Python解法：

 1 class TreeNode:
 2     def __init__(self, x):
 3         self.val = x
 4         self.left = None
 5         self.right = None
 6 
 7 
 8 class Solution:
 9     def levelOrder(self, root: TreeNode) -> List[List[int]]:
10         res = []  # 存储最终结果
11         queue = []
12         queue.append(root)
13         toBePrint = 1  # 本层将要打印的元素数量
14 
15         while root is not None and len(queue) != 0:
16             nextLvevelNum = 0  # 下一层将要打印的数量
17             childRes = []  # 存储子结果
18             while toBePrint:  # 当前层没有打印完
19                 temp = queue.pop(0)  # 取队的头元素
20                 toBePrint -= 1
21                 childRes.append(temp.val)
22 
23                 if temp.left:
24                     queue.append(temp.left)
25                     nextLvevelNum += 1
26                 if temp.right:
27                     queue.append(temp.right)
28                     nextLvevelNum += 1
29 
30             toBePrint = nextLvevelNum  # 下一层要打印的数量就是下一轮当前层要打印的数量
31             res.append(childRes)
32         return res

C++解法：

 1 struct TreeNode {
 2     int val;
 3     TreeNode *left;
 4     TreeNode *right;
 5     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 6 };
 7 
 8 class Solution {
 9 public:
10     vector<vector<int>> levelOrder(TreeNode* root) {
11         vector<vector<int>> res;
12         deque<TreeNode*> doubleQue;
13         doubleQue.push_back(root);
14         int toBePrint = 1;  // 当前层将要打印的节点数量
15         while (root != NULL && !doubleQue.empty()) {  // 当根节点非空且队列非空时
16             vector<int> childRes;
17             int nextLevelNum = 0;  // 下一层将要打印的节点数量
18             while (toBePrint != 0) {
19                 TreeNode *tempNode = doubleQue.at(0); // 取队头元素
20                 doubleQue.pop_front();  // 删除队头元素
21                 toBePrint -= 1;
22                 childRes.push_back(tempNode->val);
23 
24                 if (tempNode->left) {
25                     doubleQue.push_back(tempNode->left);
26                     nextLevelNum += 1;
27                 }
28                 if (tempNode->right) {
29                     doubleQue.push_back(tempNode->right);
30                     nextLevelNum += 1;
31                 }
32             }
33             toBePrint = nextLevelNum;
34             res.push_back(childRes);
35         }
36         return res;
37     }
38 };

推荐阅读