LeetCode102. Sequence traversal of binary tree (output by layer and unified output)

LeetCode102. Sequence traversal of binary tree

1. problem

2. Ideas

（1） What is hierarchy traversal

According to the number of layers, from small to large , The same layer accesses nodes from left to right

Realization ：（ Queue required ！）

In the i If the node on the layer x At node y Left side , be x It must be y I was interviewed before . also , In the i+1 On the floor ,x The child node of must be y The child nodes of were previously accessed .

（2） With the help of queues

Operation example ：

3. Code implementation

Output by layer , Just press in the above figure [[A] [BC] [DEF]] Format output .
Unified output , Namely [ABCDEF] The format of .

a. Output version by layer

class Solution {
    
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
    
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
    
            int size = que.size();
            vector<int> vec;
            //  Be sure to use a fixed size here size, Do not use que.size(), because que.size It's changing 
            for (int i = 0; i < size; i++) {
    //size It means traversing by sequence   Because only one layer of data is left in each queue  
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

b. Unified output and publication

Just change the code above

// In this way, sequence traversal sequence can be output , But it cannot be output by layer . 
 class Solution {
    
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
    
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        vector<int> vec;
        while (!que.empty()) {
    
            //int size = que.size();// Just remove the hierarchy 
            //for (int i = 0; i < size; i++) {
    
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                //result.push_back(vec);
                if (node->right) que.push(node->right);
            //}
        }
         result.push_back(vec);
        return result;
    }
};