牛客网 按之字形顺序打印二叉树

缘起

这也算是一道高频面试题了. 牛客网 按之字形顺序打印二叉树 

1
2
3
4
5
6
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行
按照从左到右的顺序打印，其他行以此类推。

【限制】
时间限制：1秒
空间限制：32768K

分析

没什么好说的——就是二叉树遍历的一种（【1】中也写过二叉树遍历）.

但是牛客网给出的代码原型是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        
    }
    
};

兹麻里，你不准使用树节点的深度这一概念~ 其实不用也没关系. 我们使用两个队列（vector），一个是奇数层，一个存偶数层. 奇数层生成偶数层, 偶数层生成奇数层. 这样就不需要树节点多一个深度的属性了.

下面的代码的做法就是

奇数层只保存节点, 然后while的一次循环做的事情就是

添加奇数层的结果到ans中, 然后用奇数层生成偶数层, 然后保存偶数层的结果到ans, 最后利用偶数层生成新的奇数层.

代码中需要健壮性判断. 不然会WA

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
57
58
59
60
61
62
63
64
65
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
		vector<vector<int> > ans;
		if (!pRoot) // 如果是空树的话, 直接返回一个空的结果,注意, 这里一定要特判空树,不然WA
		{
			return ans;
		}
		vector<TreeNode *> odd,even; // odd装奇数层的节点, even装偶数层的节点
		odd.push_back(pRoot); // 初始化奇数层节点
		while(!odd.empty()) // while中干的事情就是奇数层生成偶数层，然后偶数层再生成奇数层
		{
			even.clear(); // 清空偶数层
			vector<int> _odd,_even; // 用于保存奇数层结果和偶数层的结果
			for (vector<TreeNode*>::iterator i = odd.begin(); i!=odd.end(); i++)
			{
				_odd.push_back((*i)->val);
			}
			if (!_odd.empty())
			{
				ans.push_back(_odd);
			}
			for (vector<TreeNode*>::reverse_iterator i = odd.rbegin(); i!=odd.rend(); i++) // 偶数层是从右到左加入的,所以要从右到左遍历奇数层
			{
				if ((*i)->right)
				{
					even.push_back((*i)->right);
					_even.push_back((*i)->right->val);
				}
				if ((*i)->left)
				{
					even.push_back((*i)->left);
					_even.push_back((*i)->left->val);
				}
			}
			if (!_even.empty())
			{
				ans.push_back(_even);
			}
			odd.clear(); // 准备生成新的奇数层
			for (vector<TreeNode*>::reverse_iterator i = even.rbegin(); i!=even.rend(); i++) // 由偶数层生成奇数层,需要从左到右加入, 所以需要逆向遍历偶数层节点
			{
				if ((*i)->left)
				{
					odd.push_back((*i)->left);
				}
				if ((*i)->right)
				{
					odd.push_back((*i)->right);
				}
			}
		}
		return ans;
    }
};

ac情况

您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例

参考

【1】https://yfsyfs.github.io/2019/05/20/%E4%BA%8C%E5%8F%89%E6%A0%91%E9%81%8D%E5%8E%86/