【LeetCode】107 - Binary Tree Level Order Traversal II-白红宇

【LeetCode】107 - Binary Tree Level Order Traversal II

阅读量：6902 次

发布时间：2019-06-27

本文共 1321 字，大约阅读时间需要 4 分钟。

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,#,#,15,7},

3   / \  9  20    /  \   15   7

return its bottom-up level order traversal as:

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

Solution 1: 普通层次遍历，借助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
     
      
       > levelOrderBottom(TreeNode* root) {      //runtime: 8ms        vector
       
        
         > vec;        if(!root)return vec;        vector
         
           v;                queue
          
            q1,q2; q1.push(root); while(!q1.empty()){ TreeNode* temp = q1.front(); q1.pop(); v.push_back(temp->val); if (temp->left) q2.push(temp->left); if (temp->right) q2.push(temp->right); if(q1.empty()){ if (!v.empty()) vec.push_back(v); v.clear(); swap(q1, q2); } } reverse(vec.begin(),vec.end());　　　　//or vector
           
            
             > ret(vec.rbegin(),vec.rend());return ret; 　　　　 return vec; 　　　} }