AcWing 45. 之字形打印二叉树
宋标 Lv5
  2022-08-18 02:31:05 2022-08-18 02:31    

题目

请实现一个函数按照之字形顺序从上向下打印二叉树。

即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

数据范围

树中节点的数量 。

样例

输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]
    8
   / \
  12  2
     / \
    6   4
输出：[[8], [2, 12], [6, 4]]

题解

两个栈交替遍历实现

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
class Solution {
public:

    vector<vector<int>> printFromTopToBottom(TreeNode* root) {

        stack<TreeNode*> one; stack<TreeNode*> two; vector<vector<int>> ans;
        bool flag = true; 

        if (root) one.push(root);

        while (one.size() || two.size())
        {
            int layer = 0;
            vector<int> res;

            if (flag) 
            {
                // 从左到右弹出遍历
                while (one.size())
                {
                    auto t = one.top(); one.pop();
                    res.push_back(t -> val);
                    // 添加顺序从左到右
                    if (t -> left) two.push(t -> left);
                    if (t -> right) two.push(t -> right);
                }
            }
            else 
            {
                // 从右到左弹出遍历
                while (two.size())
                {
                    auto t = two.top(); two.pop();
                    res.push_back(t -> val);
                    // 添加顺序从右到左
                    if (t -> right) one.push(t -> right);
                    if (t -> left) one.push(t -> left);
                }
            }

            ans.push_back(res);
            flag = !flag;
        }

        return ans;
    }
};
 评论