LeetCode Binary Tree Zigzag Level Order Traversal

LeetCode Binary Tree Zigzag Level Order Traversal

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   7

return its zigzag level order traversal as:

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

本题还是树的层次遍历,但是稍微有点不一样,要求奇数层从左往右输出,偶数层从右往左输出。常规的层次遍历使用BFS实现,即队列,这里要求颠倒顺序,马上想到用堆栈。

维护一个left2right布尔变量,当tru时,把孩子从左往右压栈,这样下一层的输出顺序就是从右往左了;当为false时相反。这里我们还需要用到两个堆栈,分别保存当前层和下一层的结果。

talk is cheap, show you the code!

class Solution {
public:
	vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
		vector<vector<int>> ans;
		if (!root)return ans;
		bool left2right = true;
		stack<TreeNode*> stk;
		stk.push(root);
		while(!stk.empty()) {
			stack<TreeNode*> stk2;
			vector<int> cand;
			size_t n = stk.size();
			for (size_t i = 0; i < n; ++i) {
				TreeNode* top = stk.top();
				stk.pop();
				if (!top)continue;
				cand.push_back(top->val);
				if (left2right) {
					stk2.push(top->left);
					stk2.push(top->right);
				}
				else {
					stk2.push(top->right);
					stk2.push(top->left);
				}
			}
			left2right = !left2right;
			if (!cand.empty()) ans.push_back(cand);
			stk = stk2;
		}
		return ans;
	}
};

本代码提交AC,用时6MS。

Leave a Reply

Your email address will not be published. Required fields are marked *