美文网首页
Tree Binary Tree Level Order Tra

Tree Binary Tree Level Order Tra

作者: 衣忌破 | 来源:发表于2017-05-05 16:06 被阅读15次

    https://leetcode.com/problems/binary-tree-level-order-traversal-ii/#/description

    这题不难主要贴出使用vector和queue的两种算法(利用queue思路比较巧妙同时也比前者快)。

    /**
     * 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>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> vecResult;
            vector<vector<int>> res = coutVec0(root, 0, vecResult);
            reverse(res.begin(), res.end());
            return res;
        }
        vector<vector<int>> coutVec0(TreeNode* root,int level ,vector<vector<int>>& vecResult){
            if(!root){
                return vecResult;
            }
            
           if(level < vecResult.size()){
                //  vecResult[vecResult.size()-1-level].push_back(root->val);
                vecResult[level].push_back(root->val);
           }else if(level == vecResult.size()){
                  vector<int> vec;
                  vec.push_back(root->val);
                //   vecResult.insert(vecResult.begin(), vec);
                vecResult.push_back(vec);
            }
            ++level;
            coutVec0(root->left, level, vecResult);
            coutVec0(root->right, level, vecResult);
            return vecResult;
         }
    };
    
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) {
            return res;
        }
        queue<TreeNode*> t;
        t.push(root);
        while (!t.empty()) { //将"某一层"的节点的子节点都放到队列中,并把原来的节点出列
            vector<int> tn;
            int cnt = t.size();
            for (unsigned int i = 0; i < cnt; ++i) {
                TreeNode *cur = t.front();
                tn.push_back(cur->val);
                t.pop();
                if (cur->left)
                        t.push(cur->left);
                if (cur->right)
                    t.push(cur->right);
            }
            //do not use insert() here,it cost too much time.
            //use reverse() insteadly
            res.push_back(tn);
        }
        reverse(res.begin(), res.end());
        return res;
    }
    

    相关文章

      网友评论

          本文标题:Tree Binary Tree Level Order Tra

          本文链接:https://www.haomeiwen.com/subject/wjhstxtx.html