这题让按照之字形顺序打印二叉树，也就是先从左往右打印，接着下一层在从右往左打印，在下一层又从左往右打印……，就这样左右来回交替的方式。
这里我们可以使用双端队列：
- 如果当前层是从
左往右打印，那么它的子节点要从左往右添加到队列的尾部。 - 如果当前层是从
右往左打印，那么它的子节点要从右往左添加到队列的头部。
如下图所示：
public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
if (root == null)
return ans;
// 双端队列，两边都可以操作
Deque<TreeNode> dq = new LinkedList<>();
dq.addFirst(root);// 添加到队列的头
while (!dq.isEmpty()) {
// 存储每层的节点
ArrayList<Integer> levelList = new ArrayList<>();
int cnt = dq.size();// 当前层节点的个数
TreeNode cur;
for (int i = 0; i < cnt; i++) {
// 根据第几层来决定是从左往右遍历还是从右往左遍历
if (ans.size() % 2 == 0) {
// 从左边往右边打印
// 移除队列头部的元素，如果子节点不为空加入到队列的尾部
cur = dq.removeFirst();
// 注意顺序，先判断左子树再判断右子树，添加到尾部
if (cur.left != null)
dq.addLast(cur.left);
if (cur.right != null)
dq.addLast(cur.right);
} else {
// 从右边往左边打印
// 移除队列尾部的元素，如果子节点不为空加入到队列的头部
cur = dq.removeLast();
// 注意顺序，先判断右子树再判断左子树，添加到头部
if (cur.right != null)
dq.addFirst(cur.right);
if (cur.left != null)
dq.addFirst(cur.left);
}
levelList.add(cur.val);// 记录当前层的节点
}
ans.add(levelList);
}
return ans;
}
public:
vector<vector<int>> Print(TreeNode *pRoot) {
vector<vector<int>> ans;
if (pRoot == nullptr)
return ans;
// 双端队列，两边都可以操作
deque<TreeNode *> dq;
dq.push_back(pRoot);// 添加到队列的头
while (!dq.empty()) {
// 存储每层的节点
vector<int> levelList;
int cnt = dq.size();// 当前层节点的个数
TreeNode *cur;
for (int i = 0; i < cnt; i++) {
// 根据第几层来决定是从左往右遍历还是从右往左遍历
if (ans.size() % 2 == 0) {
// 从左边往右边打印
// 移除队列头部的元素，如果子节点不为空加入到队列的尾部
cur = dq.front();
dq.pop_front();
// 注意顺序，先判断左子树再判断右子树，添加到尾部
if (cur->left)
dq.push_back(cur->left);
if (cur->right)
dq.push_back(cur->right);
} else {
// 从右边往左边打印
// 移除队列尾部的元素，如果子节点不为空加入到队列的头部
cur = dq.back();
dq.pop_back();
// 注意顺序，先判断右子树再判断左子树，添加到头部
if (cur->right)
dq.push_front(cur->right);
if (cur->left)
dq.push_front(cur->left);
}
levelList.push_back(cur->val);// 记录当前层的节点
}
ans.push_back(levelList);
}
return ans;
}
这题要求的时间复杂度是 O(n) ，如果没有这个要求，我们还可以有一种写法更简单的方式，只不过时间复杂度要高一些，因为插入的时候要在头部插入，可以看下 java 代码：
public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
if (root == null)
return ans;
Queue<TreeNode> q = new LinkedList<>();// 创建队列
q.add(root);// 根节点添加到队列中
boolean leftToRight = true;// 第一步先从左往右打印
while (!q.isEmpty()) {
// 当前层的节点个数
int cnt = q.size();
ArrayList<Integer> mList = new ArrayList<>();// 当前层的集合
// 遍历这一行的所有节点
for (int i = 0; i < cnt; i++) {
TreeNode cur = q.poll();
// 判断是从左往右打印还是从右往左打印。
if (leftToRight) {// 从左往右添加到后面
mList.add(cur.val);
} else {// 从右往左添加到前面
mList.add(0, cur.val);
}
// 左右子节点如果不为空会被加入到队列中
if (cur.left != null)
q.add(cur.left);
if (cur.right != null)
q.add(cur.right);
}
ans.add(mList);
leftToRight = !leftToRight;// 下一步更改方向
}
return ans;
}
京公网安备 11010502036488号