Leetcode Study Day 40

Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Example 2:

Input: root = [1]
Output: [[1]]
Example 3:

Input: root = []
Output: []

Solution

Like other breadth first search questions, we use a queue to store the nodes in the same level. We first push the root into the queue. Then we use a while loop to check if the queue is empty. If it is not empty, we get the size of the queue. The size of the queue is the number of nodes in the same level. We use a for loop to pop the nodes in the queue and add the value of the node to the sum. Then we check if the node has left child or right child. If it has, we push the child into the queue. After the for loop, we push the singleLevel vector into the answer vector. Then we return the answer vector.

/**
 * 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>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> treeQ;
        if (!root) return ans;
        treeQ.push(root);
        while(!treeQ.empty()){
            vector<int> singleLevel;
            int size = treeQ.size();
            for (int i = 0; i<size; i++){
                TreeNode* node = treeQ.front();
                treeQ.pop();
                if (node->left) treeQ.push(node->left);
                if (node->right) treeQ.push(node->right);
                singleLevel.push_back(node->val);
            }
            ans.push_back(singleLevel);

        }
        return ans;
    }
};

Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:

Input: root = [1]
Output: [[1]]
Example 3:

Input: root = []
Output: []
 

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

My solution

This question’s solution is quite similar to the previous one, except for I adding a boolean variable to determine whether to reverse the single vector. If the boolean variable is true, we reverse the single vector. Then we push the single vector into the answer vector. Then we return the answer vector.

/**
 * 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>> ans;
        queue <TreeNode*> treeQ;
        if(!root) return ans;
        treeQ.push(root);
        bool flag = false;
        while(!treeQ.empty()){
            int size = treeQ.size();
            vector <int> single;
            for(int i = 0; i < size; i++){
                TreeNode* node = treeQ.front();
                treeQ.pop();
                single.push_back(node->val);
                if(node->left) treeQ.push(node->left);
                if(node->right) treeQ.push(node->right);
            }
            if (flag) reverse(single.begin(),single.end());
            ans.push_back(single);
            flag = !flag;
        }
        return ans;
    }
};