{"id":2168,"date":"2016-09-07T13:54:03","date_gmt":"2016-09-07T05:54:03","guid":{"rendered":"http:\/\/boweihe.me\/?p=2168"},"modified":"2016-09-07T13:54:03","modified_gmt":"2016-09-07T05:54:03","slug":"leetcode-103-binary-tree-zigzag-level-order-traversal","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2168","title":{"rendered":"LeetCode 103. Binary Tree Zigzag Level Order Traversal"},"content":{"rendered":"

Given a binary tree, return the zigzag level order<\/i> traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
\nFor example:
\nGiven binary tree [3,9,20,null,null,15,7]<\/code>,<\/p>\n

    3\n   \/ \\\n  9  20\n    \/  \\\n   15   7\n<\/pre>\n
return its zigzag level order traversal as:<\/p>\n
[\n  [3],\n  [20,9],\n  [15,7]\n]<\/pre>\n
\u601d\u8def<\/h3>\n
\u8bb0\u4f4f\u4e0a\u4e00\u884c\u7684\u8f93\u51fa\uff08\u7ed3\u679c\uff09\u8282\u70b9\uff0c\u6bcf\u4e00\u6b21\u4ece\u540e\u5f80\u524d\u8bfb\u51fa\u4e0b\u4e00\u884c\uff0c\u8fd9\u6837\u7b2c2,4,6\u6b21\u8bfb\u7684\u65f6\u5019\u5176\u5b9e\u5c31\u4f1a\u7ffb\u8f6c\u6210\u6b63\u5411\u4e86\u3002\u552f\u4e00\u7684\u95ee\u9898\u662f\u5de6\u53f3\u5b50\u8282\u70b9\u5199\u5165\u4e0b\u4e00\u884c\u7684\u987a\u5e8f\uff0c\u6309\u7167\u5f53\u524d\u987a\u5e8f\u533a\u5206\u4e00\u4e0b\u5c31\u884c\u3002\u4e0d\u662f\u5de6\u53f3\u5de6\u53f3\uff0c\u5c31\u662f\u53f3\u5de6\u53f3\u5de6\uff0c\u5177\u4f53\u770bcode\u5427\u3002<\/p>\n
\u4ee3\u7801<\/h3>\n
\/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n *\/\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        vector<vector<int>> result;\n        if(root == NULL)\n            return result;\n        vector<TreeNode*>* currRow = new vector<TreeNode*>();\n        vector<TreeNode*>* nextRow = new vector<TreeNode*>();\n        bool direction = true;  \/\/true: R,L,R,L,...; false:L,R,L,R,...\n        currRow->push_back(root);\n        while(!currRow->empty()){\n            \/\/Output current row\n            vector<int> currRowResult;\n            for(int i=0; i<currRow->size(); i++){\n                currRowResult.push_back( (*currRow)[i]->val );\n            }\n            result.push_back(currRowResult);\n            \/\/\n            for(int i=currRow->size()-1; i>=0; i--){\n                TreeNode* currNode = (*currRow)[i];\n                if(direction){\n                    if(currNode->right != NULL)\n                        nextRow->push_back(currNode->right);\n                    if(currNode->left != NULL)\n                        nextRow->push_back(currNode->left);\n                } else {\n                    if(currNode->left != NULL)\n                        nextRow->push_back(currNode->left);\n                    if(currNode->right != NULL)\n                        nextRow->push_back(currNode->right);\n                }\n            }\n            \/\/swap currRow and nextRow\n            vector<TreeNode*>* temp = currRow;\n            currRow = nextRow;\n            nextRow = temp;\n            nextRow->clear();\n            direction = !direction;\n        }\n        return result;\n    }\n};<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 3 \/ \\ 9 20 \/ \\ 15 7 return its zigzag level order traversal as: [ [3], [20,9], […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66,133],"class_list":["post-2168","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj","tag-133"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2168","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2168"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2168\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2168"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2168"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}