103 Binary Tree Zigzag Level Order Traversal

题目

103 Binary Tree Zigzag Level Order Traversal

题解

题目要求：给定一棵树，返回它的zigzag遍历结果。zigzag遍历指从根节点开始，交替地使用从左到右、从右到左这两种方式遍历树的每一层。

因为是以交替方向的方式遍历树，所以当前层次的遍历方向总是与下一层次的方向相反。因此，在遍历当前层次的节点时，需要把下一层的节点，也就是当前节点的子节点，以与当前遍历方向相反的方向记录下来。这类反向操作，十分适合由后入先出的栈来完成：把下一层的节点逐个push到一个栈里再对这个栈进行遍历，即可实现反向遍历。交替方向的实现可以使用两个栈来完成，一个栈用来进行从左到右遍历，另一个栈用来进行从右到左遍历。在对其中一个栈进行遍历的时候，把遍历到的节点的子节点push进另外一个栈中。这样只要交替地遍历两个栈，就能实现树的zigzag层次访问。

代码

class Solution {
public:
	vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
		vector<vector<int>> result;

		stack<TreeNode*> leftToRight;
		stack<TreeNode*> rightToLeft;

		if (root != NULL) {
			leftToRight.push(root);
		}
		TreeNode* current = NULL;
		while (!(leftToRight.empty() && rightToLeft.empty()))
		{
			if (!leftToRight.empty()) {
				result.push_back(vector<int>());
			}
			while (!leftToRight.empty())
			{
				current = leftToRight.top();
				if (current->left != NULL) {
					rightToLeft.push(current->left);
				}
				if (current->right != NULL) {
					rightToLeft.push(current->right);
				}

				result.back().push_back(current->val);
				leftToRight.pop();
			}

			if (!rightToLeft.empty()) {
				result.push_back(vector<int>());
			}
			while (!rightToLeft.empty())
			{
				current = rightToLeft.top();
				if (current->right != NULL) {
					leftToRight.push(current->right);
				}
				if (current->left != NULL) {
					leftToRight.push(current->left);
				}

				result.back().push_back(current->val);
				rightToLeft.pop();
			}
		}

		return result;
	}
};