LeetCode OJ--Binary Tree Level Order Traversal

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

树的层序遍历，使用队列

由于树不是满的，还要分出每一层来，刚开始给缺少的节点用dummy节点代替，结果超时了。

vector<vector<int> > levelOrder(TreeNode *root) {

        vector<vector<int> > ans;

        if(root == NULL)

            return ans;

        int num = ,num2 = ;

        queue<TreeNode *> myQueue;

        myQueue.push(root);

        TreeNode *nodeFront;

        TreeNode *dummy = new TreeNode(-);

        vector<int> onePiece;

        while(!myQueue.empty())

        {

            nodeFront = myQueue.front();

            myQueue.pop();

            num--;

            if(nodeFront != dummy)

            {

                onePiece.push_back(nodeFront->val);

                if(nodeFront->left)

                    myQueue.push(nodeFront->left);

                else

                    myQueue.push(dummy);

                if(nodeFront->right)

                    myQueue.push(nodeFront->right);

                else

                    myQueue.push(dummy);

            }

            else

            {

                myQueue.push(dummy);

                myQueue.push(dummy);

            }

            if(num == )

            {

                if(onePiece.empty())

                break;

                ans.push_back(onePiece);

                onePiece.clear();

                num2 = num2*;

                num = num2;

            }

        }

        return ans;

    }

改进的话，对缺失的节点进行计数，则计算出下一层应该有多少个节点来，如下。

    vector<vector<int> > levelOrder(TreeNode *root) {

        vector<vector<int> > ans;

        if(root == NULL)

            return ans;

        int num = ,num2 = ,nullNum = ,nullNumAcc = ;

        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 == )

            {

                if(onePiece.empty())

                    break;

                ans.push_back(onePiece);

                onePiece.clear();

                num2 = num2*;

                nullNumAcc = nullNumAcc* + nullNum;

                num = num2 - nullNumAcc;

                nullNum = ;

            }

        }

        return ans;

    }

巴特西

LeetCode OJ--Binary Tree Level Order Traversal

最新文章

热门文章