廖家龙的博客网站
剑指Offer_32_从上到下打印二叉树
廖家龙 用心听，不照做
  2019-06-30 13:56:00   2024-07-19 11:15:42    1k 字  4 分钟

题目1描述：不分行从上到下打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//二叉树的层序遍历

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

示例：

给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
   
返回：[3,9,20,15,7]

提示：节点总数 <= 1000

解法1：队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

//每次打印一个节点的时候，如果该节点有子节点，则把该节点的子节点放到一个队列的队尾，接下来到队列的头部取出最早进入队列的节点，重复前面的操作，直至队列中所有的节点都被打印出来
    vector<int> levelOrder(TreeNode* root) {

        vector<int> ret;  //定义一个容器
        queue<TreeNode* > que;  //定义一个队列

        if (root != NULL) que.push(root);

        while (!que.empty()) {
            
            TreeNode *node = que.front();  //node指向队列的首节点
            
            if (node->left != NULL) que.push(node->left);
            if (node->right != NULL) que.push(node->right);

            que.pop();
            ret.push_back(node->val);
        }
        return ret;
    }
};

❗️LeetCode_102_二叉树的层序遍历

题目2描述：分行从上到下打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

示例：

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

提示：节点总数 <= 1000

解法1：队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        
        queue<TreeNode* > que;  //定义一个队列
        vector<vector<int>> ret;  //定义一个嵌套容器

        if (root != NULL) que.push(root);  //初始化

        while(!que.empty()) {

            int sz = que.size();  //本层节点个数

            vector<int> ret1;  //定义一个容器

            for(int i = 0; i < sz; ++i) { 

                TreeNode* node = que.front();
                if (node->left != NULL) que.push(node->left);  //压入左节点
                if (node->right != NULL) que.push(node->right); //压入右节点

                que.pop();
                ret1.push_back(node->val);
            }
            ret.push_back(ret1);
        }
        return ret;
    }
};

题目3描述：之字形打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

示例：

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

提示：节点总数 <= 1000

解法1：两个栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

//按之字形顺序打印二叉树需要两个栈，我们在打印某一层的节点时，把下一层的子节点保存到相应的栈里
//如果当前打印的是奇数层（第一层、第三层等），则先保存左子节点再保存右子节点到第一个栈里
//如果当前打印的是偶数层（第二层、第四层等），则先保存右子节点再保存左子节点到第二个栈里
    vector<vector<int>> levelOrder(TreeNode* root) {

        stack<TreeNode* > left, right;  //定义两个栈
        vector<vector<int>> ans;  //定义一个嵌套容器

        if (root != nullptr) left.push(root);  //初始化：先将根节点放到左栈中

        while(!left.empty() || !right.empty()) {

            vector<int> ans1;  //定义一个容器

            if (!left.empty()) {  //if else是不能去掉的

                while (!left.empty()) {

                    TreeNode* nodeleft = left.top();
                    
                    if (nodeleft->left != nullptr) right.push(nodeleft->left);
                    if (nodeleft->right != nullptr) right.push(nodeleft->right);

                    left.pop();
                    ans1.push_back(nodeleft->val);
                }
            } else {

                while (!right.empty()) {

                    TreeNode* noderight = right.top();
                    
                    if (noderight->right != nullptr) left.push(noderight->right);
                    if (noderight->left != nullptr) left.push(noderight->left);

                    right.pop();
                    ans1.push_back(noderight->val);
                }
            }
            ans.push_back(ans1);
        }
        return ans;
    }
};
  1. 1. 题目1描述：不分行从上到下打印二叉树
    1. 1.1. 解法1：队列
  2. 2. 题目2描述：分行从上到下打印二叉树
    1. 2.1. 解法1：队列
  3. 3. 题目3描述：之字形打印二叉树
    1. 3.1. 解法1：两个栈
  1. 1. 题目1描述：不分行从上到下打印二叉树
    1. 1.1. 解法1：队列
  2. 2. 题目2描述：分行从上到下打印二叉树
    1. 2.1. 解法1：队列
  3. 3. 题目3描述：之字形打印二叉树
    1. 3.1. 解法1：两个栈