之字形打印二叉树（Python and C++解法）

题目：

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-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         falg = True  # 奇偶标志位，True为奇
14 
15         while root is not None and queue:
16             lenQueue = len(queue)
17             childRes = []  # 存储每一层层结果
18 
19             while lenQueue > 0:
20                 if falg:  # 如果是奇数层
21                     tempNode = queue.pop(0)  # 奇数层从左到右打印元素
22                     if tempNode.left:  # 下一层，即偶数层从左到右添加到队列
23                         queue.append(tempNode.left)
24                     if tempNode.right:
25                         queue.append(tempNode.right)
26                 else:  # 如果是偶数层
27                     tempNode = queue.pop()  # 偶数层从右到左打印元素
28                     if tempNode.right:  # 下一层，即奇数层从右到左添加到队列
29                         queue.insert(0, tempNode.right)  # 注意添加的顺序
30                     if tempNode.left:
31                         queue.insert(0, tempNode.left)
32                 childRes.append(tempNode.val)
33                 lenQueue -= 1
34             res.append(childRes)
35             falg = not falg  # 奇偶层变换
36         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         bool flag = true;  // 奇偶行标志位
15 
16         while (root != NULL && !doubleQue.empty()) {
17             vector<int> childRes;
18             int lenQueue = doubleQue.size();  // 计算每一层队列的长度(元素的数量)
19             while (lenQueue) {
20                 if (flag) {  // 如果是奇数层
21                     TreeNode *tempNode = doubleQue.front();  // 奇数层从左向右打印元素
22                     doubleQue.pop_front();  // 删除队列头部元素
23                     childRes.push_back(tempNode->val);
24                     if (tempNode->left)  // 偶数层从左到右添加到队列
25                         doubleQue.push_back(tempNode->left);
26                     if (tempNode->right)
27                         doubleQue.push_back(tempNode->right);
28                 }
29                 else {  // 如果是偶数层
30                     TreeNode *tempNode = doubleQue.back();  // 偶数层从右向左打印元素
31                     doubleQue.pop_back();  // 删除队列尾部元素
32                     childRes.push_back(tempNode->val);
33                     if (tempNode->right)  // 奇数层从右向左添加到队列
34                         doubleQue.push_front(tempNode->right);  // 添加到头部
35                     if (tempNode->left)
36                         doubleQue.push_front(tempNode->left);
37                 }
38                 lenQueue -= 1;
39             }
40             res.push_back(childRes);
41             flag = !flag;
42         }
43         return res;
44     }
45 };