Binary Tree Zigzag Level Order T

Binary Tree Zigzag Level Order Traversal.png

解題思路 ：

主要是 BFS 用 queue 來實現 level order traversal 只是其中多加了一個 boolean 變數來決定是否要反向放入某一層的數值 我用 xor 來做 boolean 值的修改 另外 c++ 有內建的 reverse 函數 只要放入 vector 的 begin 跟 end 即可使用

C++ code :

<pre><code>
/**

• Definition of TreeNode:
• class TreeNode {
• public:

• int val;
  

• TreeNode *left, *right;
  

• TreeNode(int val) {
  

•     this->val = val;
  

•     this->left = this->right = NULL;
  

• }
  

• }
  */

class Solution {

/**
 * @param root: The root of binary tree.
 * @return: A list of lists of integer include 
 *          the zigzag level order traversal of its nodes' values 
 */

public:

vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
    // write your code here
    vector<vector<int>> res;
    if(!root) return res;
    vector<int> tmp;
    queue<TreeNode*> Q;
    Q.push(root);
    bool leftToRight = false;
    while(!Q.empty())
    {
        int n = Q.size();
        for(int i = 0; i < n; i++)
        {
            TreeNode *node = Q.front();
            Q.pop();
            tmp.push_back(node->val);
            if(node->left) Q.push(node->left);
            if(node->right) Q.push(node->right);
        }
        leftToRight ^= 1;
        if(!leftToRight) reverse(tmp.begin(), tmp.end());
        res.emplace_back(tmp);
        tmp.clear();
    }
    return res;
}

};