首页 > 其他 > 详细

LeetCode OJ--Binary Tree Level Order Traversal II

时间:2014-02-15 16:27:20      阅读:393      评论:0      收藏:0      [点我收藏+]

http://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/

树的层序遍历,和上一道题相比,对结果做一个顺序调整 reverse()

bubuko.com,布布扣
/**
 * Definition for binary tree
 * 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> > ans;
        if(root == NULL)
            return ans;
        int num = 1,num2 = 1,nullNum = 0,nullNumAcc = 0;
        queue<TreeNode *> myQueue;
        myQueue.push(root);
        TreeNode *nodeFront;

        vector<int> onePiece;
        while(!myQueue.empty())
        {
            nodeFront = myQueue.front();
            myQueue.pop();
            num--;
             
            onePiece.push_back(nodeFront->val);
            if(nodeFront->left)
                myQueue.push(nodeFront->left);
            else
                nullNum++;
            if(nodeFront->right)
                myQueue.push(nodeFront->right);
            else
                nullNum++;
             
            if(num == 0)
            {
                if(onePiece.empty())
                    break;
                ans.push_back(onePiece);
                onePiece.clear();
                num2 = num2*2;
                nullNumAcc = nullNumAcc*2 + nullNum;
                num = num2 - nullNumAcc; 
                nullNum = 0;
            }
        }

        reverse(ans.begin(),ans.end());
        return ans; 
    }        
};
bubuko.com,布布扣

LeetCode OJ--Binary Tree Level Order Traversal II

原文:http://www.cnblogs.com/qingcheng/p/3550449.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!