【Leetcode】102. Binary Tree Level Order Traversal

拼搏现实的明天。 2022-02-19 05:04 140阅读 0赞

Given a binary tree, return the *level order* traversal of its nodes' values. (ie, from left to right, level by level).

For example:  
Given binary tree `[3,9,20,null,null,15,7]`,

3
       / \
      9  20
        /  \
       15   7

return its level order traversal as:

[
      [3],
      [9,20],
      [15,7]
    ]

题目大意：

将二叉树按照层数输入到vector中。

解题思路：

*  STL容器-deque

deque双向开口可进可出的容器，deque创造了内存连续的假象。其实deque由一段一段构成 ,他是分段连续,而不是内存连续 当走向段的尾端时候自动跳到下一段 所以支持迭代器++ 操作,自动跳到下一段的方法由operator++实现。

int main()
    {
        deque<int> c = {1,2,3,4,5};
        deque<int> c1;
        
        // 赋值初始化
        c1.assign(c.begin(),c.end());
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "assign()" <<endl;
    
        //在尾部插入
        c1.push_back(6);
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "push_back()" <<endl;
        
        //头插入
        c1.push_front(0);
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "push_front()" <<endl;
        
        //弹尾元素
        c1.pop_back();
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "pop_back()" <<endl;
        
        //弹头元素
        c1.pop_front();
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "pop_front()" <<endl;
        
        //指定位置插入元素
        c1.insert(c1.begin()+3, 10);
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "insert()" <<endl;
        
        //删除指定位置元素
        c1.erase(c1.begin()+3);
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "erase()" <<endl;
    
        //清空deque
        c.clear();
        for (auto i: c) {
            cout<< i << ",";
        }
        cout << "clear()" <<endl;
        
        //构造
        c1.emplace(c1.end(), 100);
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "emplace()" <<endl;
        
        //头位置插入元素
        c1.emplace_front(111);
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "emplace_front()" <<endl;
        
        //尾位置插入元素
        c1.emplace_back(111);
        for (auto i: c1) {
            cout<< i << ",";
        }
        cout << "emplace_back()" <<endl;
        
        //交换
        c.swap(c1);
        for (auto i: c) {
            cout<< i << ",";
        }
        cout << "swap()" <<endl;
        
        int tmp;
        tmp = c.front();
        cout<<"第一个元素"<< tmp << endl;
        
        tmp = c.back();
        cout<<"最后一个元素"<< tmp << endl;
        
        tmp = c.at(1);
        cout<<"指定下标元素"<< tmp << endl;
        
        tmp = c[1];
        cout<<"指定[]下标元素"<< tmp << endl;
    
        return 0;
    }

应该使用BFS来解决，时间空间复杂度最小。由于需要在队列的头部取值，需要使用deque容器。

根据vector中存储的节点，分别添加该位置的左右节点。

vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        deque<TreeNode*> q;
        
        if (root)   q.push_front(root);        
        while (q.size()) {
            ret.resize(ret.size() + 1);
            int og_size = q.size(); 
                
            for (int i = 0, og_size = q.size(); i != og_size; i++)  {
                auto node = q.front();
                ret.back().push_back(node->val);
        
                if (node->left)     q.push_back(node->left);
                if (node->right)    q.push_back(node->right);   
                q.pop_front();
            }
        }
        return ret;
    }