[LeetCode] 103. Binary Tree Zigzag Level Order Traversal

轉自LeetCode

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]
]

<Solution>

這題一樣是要 level order traversal，但第一列是從左至右，然後第二列是要從右至左，但三列要從左至右，這樣的規則下去

一樣可以使用 Binary Tree Level Order Traversal 的方式去解

只是在偶數列的時候，要反轉一下答案，這樣就可以了

code 如下

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
	if(!root) {
	return vector<vector<int>>();
	}
	vector<vector<int>> ans;
	vector<int> out;
	queue<TreeNode *> nodeQue;
	nodeQue.push(root);
	bool needReverse = false;
	while(!nodeQue.empty()) {
	int size = nodeQue.size();
	out.clear();
	for(int i = 0; i < size; i++) {
	TreeNode *tmpNode = nodeQue.front();
	nodeQue.pop();
	out.push_back(tmpNode->val);
	if(tmpNode->left) {
	nodeQue.push(tmpNode->left);
	}
	if(tmpNode->right) {
	nodeQue.push(tmpNode->right);
	}
	}
	if(needReverse) {
	reverse(out.begin(), out.end());
	}
	ans.push_back(out);
	needReverse = !needReverse;
	}
	return ans;
	}
	};

view raw binaryTreeZigZagLevelOrderTraversal_1.cpp hosted with ❤ by GitHub

如果不想用 reverse() 來完成，還有使用 list 的做法

用題目的例子來說明

round1:

list : [3], size = 1, don't reverse

=> 從 list 的後面拿 node，此時 list 為空

=> level order : 3

=> 先檢查當前 node 的 left child 是否為空，不為空就放到 list，注意是用 push_front，list : [9]

=> 再檢查 node 的 right child 是否為空，不為空放到 list，注意是用 push_front，list : [20, 9]

routd2:

list : [20, 9], size = 2, need reverse

=> 從 list 的前面拿 node，list = [9]

=> level order : 20

=> 先檢查 right child 是否為空，不為空放到 list，注意是用 push_back，list : [9, 7]

=> 先檢查 left child 是否為空，不為空放到 list，注意是用 push_back，list : [9, 7, 15]

=> 從 list 的前面拿 node，list = [7, 15]

=> level order : 20，9

=> 先檢查 right child 是否為空，不為空放到 list，注意是用 push_back，list : [7, 15]

=> 先檢查 left child 是否為空，不為空放到 list，注意是用 push_back，list : [7, 15]

round3:

list : [7, 15], size = 2, don't reverse

=> 從 list 的後面拿 node，list : [7]

=> level order : 15

=> 先檢查 left child 是否為空，不為空就放到 list，注意是用 push_front，list : [15]

=> 再檢查 right child 是否為空，不為空放到 list，注意是用 push_front，list : [15]

=> 從 list 的後面拿 node，list : []

=> level order : 15，7

=> 先檢查 left child 是否為空，不為空就放到 list，注意是用 push_front，list : []

=> 再檢查 right child 是否為空，不為空放到 list，注意是用 push_front，list : []

根據以上方式，需要多用一個 bool 來判斷是否要 reverse，然後做對應的操作方式即可

code 如下

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
	if(!root) {
	return vector<vector<int>>();
	}
	list<TreeNode *> nodeList;
	nodeList.push_front(root);
	vector<vector<int>> ans;
	vector<int> out;
	bool needReverse = false;
	while(!nodeList.empty()) {
	int size = nodeList.size();
	out.clear();
	if(needReverse) {
	for(int i = 0; i < size; i++) {
	TreeNode *tmpNode = nodeList.front();
	nodeList.pop_front();
	out.push_back(tmpNode->val);
	//> put child node into list from right to left
	if(tmpNode->right) {
	nodeList.push_back(tmpNode->right);
	}
	if(tmpNode->left) {
	nodeList.push_back(tmpNode->left);
	}
	}
	}
	else {
	for(int i = 0; i < size; i++) {
	TreeNode *tmpNode = nodeList.back();
	nodeList.pop_back();
	out.push_back(tmpNode->val);
	//> put child node into list from left to right
	if(tmpNode->left) {
	nodeList.push_front(tmpNode->left);
	}
	if(tmpNode->right) {
	nodeList.push_front(tmpNode->right);
	}
	}
	}
	ans.push_back(out);
	needReverse = !needReverse;
	}
	return ans;
	}
	};

view raw binaryTreeZigZagLevelOrderTraversal_2.cpp hosted with ❤ by GitHub