LeetCode 107. Binary Tree Level Order Traversal II

ShenduCC

发布于 2018-07-24 16:01:35

2710

发布于 2018-07-24 16:01:35

文章被收录于专栏：算法修养

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

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

return its bottom-up level order traversal as:

c++:

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        
       queue<TreeNode*> q;
       queue<int> q2;
       vector<vector<int> > ans;
       if(root==NULL)
           return ans;
       q.push(root);q2.push(0);
       vector<int> res;
       int j=-1;
       while(!q.empty())
       {
           TreeNode* term = q.front();
           int i = q2.front();
           if(i==j+2)
           {
               ans.push_back(res);
               res.clear();
               j++;
           }
           res.push_back(term->val);     
           q.pop();q2.pop();
           if(term->left!=NULL)
           { q.push(term->left);q2.push(i+1);}
           if(term->right!=NULL)
           { q.push(term->right);q2.push(i+1);}
       }
       if(!res.empty())
           ans.push_back(res);
        
        vector<vector<int> > result;
        int n = ans.size()-1;
        for(int i=ans.size()-1;i>=0;i--)
        {
            result.push_back(ans[i]);
        }
        
       return result;
        
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-06-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树