博文中会简要介绍Leetcode P0103题目分析及解题思路。
“Binary Tree Zigzag Level Order Traversal”是一道比较基础的树问题，算是p0102的变形题，层遍历一般使用广度优先搜索，即BFS，就可以解决。
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7return its level order traversal as:
[ [3], [20,9], [15,7] ]
这道题和p0102不同的地方是遍历顺序，最简单的解法是层遍历完毕，翻转数组（链表）即可。相对优化的算法是维护两个栈，轮流存储，当从左到右遍历时，从左至右压栈，则下一层通过出栈可以实现从右到左遍历，然后此时从右至左压栈，这样一来再下一层又可以实现从左至右的遍历，以此类推。
Java代码实现了维护两个栈轮流存储的解法，C++代码则是常规的BFS解法。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
if (root == null)
return levels;
Deque<TreeNode> stack1 = new LinkedList<>();
Deque<TreeNode> stack2 = new LinkedList<>();
List<Integer> level = new ArrayList<>();
int numOfNodesInNextLevel = 0, numOfNodesInCurrentLevel = 1, zigzag = 0;
Deque<TreeNode>[] deques = new Deque[2];
deques[0] = stack1;
deques[1] = stack2;
Deque<TreeNode> deque = deques[zigzag];
deque.offerFirst(root);
while (!deque.isEmpty()) {
TreeNode curr = deque.pollFirst();
if (zigzag == 0)
numOfNodesInNextLevel += pushTo(deques[1], curr.left, curr.right);
else
numOfNodesInNextLevel += pushTo(deques[0], curr.right, curr.left);
level.add(curr.val);
if (level.size() == numOfNodesInCurrentLevel) {
levels.add(new ArrayList<>(level));
level.clear();
// Reset
numOfNodesInCurrentLevel = numOfNodesInNextLevel;
numOfNodesInNextLevel = 0;
// Reverse deque
zigzag = (zigzag+1)%2;
deque = deques[zigzag];
}
}
return levels;
}
private int pushTo(Deque<TreeNode> stack, TreeNode first, TreeNode second) {
int nodes = 0;
if (first != null) {
stack.offerFirst(first);
++nodes;
}
if (second != null) {
stack.offerFirst(second);
++nodes;
}
return nodes;
}
}
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> levels;
if (root == NULL)
return levels;
queue<TreeNode*> node_queue;
vector<int> level;
int num_in_curr_level = 1, num_in_next_level = 0, zigzag = false;
node_queue.push(root);
while (!node_queue.empty()) {
TreeNode *curr = node_queue.front();
node_queue.pop();
if (curr->left != NULL) {
node_queue.push(curr->left);
++num_in_next_level;
}
if (curr->right != NULL) {
node_queue.push(curr->right);
++num_in_next_level;
}
level.push_back(curr->val);
if (level.size() == num_in_curr_level) {
vector<int> copied(level.size(), 0);
for (int idx=0; idx<level.size(); ++idx) {
if (!zigzag)
copied[idx] = level[idx];
else
copied[level.size()-1-idx] = level[idx];
}
levels.push_back(copied);
level.clear();
num_in_curr_level = num_in_next_level;
num_in_next_level = 0;
zigzag = !zigzag;
}
}
return levels;
}
};