admin 管理员组

文章数量: 1086866

leetcode【102，103】Binary Tree Level Order Traversal Binary Tree Zigzag Level Order Traversal

问题描述（102）：

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

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

    3/ \9  20/  \15   7

 

return its level order traversal as:

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

源码（102）：

和剑指offer的第32题的第二小问一摸一样，用一个队列，注意换行就行。效率还算可以，时间93%，空间还是100%。

/*** 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<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;if(!root)   return result;vector<int> rows;queue<TreeNode*> help;int behind = 1, nextlevel=0;help.push(root);while(!help.empty()){TreeNode *tmp = help.front();help.pop();rows.push_back(tmp->val);if(tmp->left){help.push(tmp->left);nextlevel++;}if(tmp->right){help.push(tmp->right);nextlevel++;}behind--;if(!behind){behind = nextlevel;nextlevel = 0;result.push_back(rows);rows.clear();}}return result;}
};

问题描述（103）：

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],[15,7]
]

源码（103）：

和剑指offer的第32题的第二小问一摸一样，用两个栈。时间84%，空间100%。

/*** 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<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> result;if(!root)   return result;vector<int> rows;stack<TreeNode*> stack[2];stack[0].push(root);int cur = 0, next = 1;while(!stack[0].empty() || !stack[1].empty()){TreeNode* tmp = stack[cur].top();stack[cur].pop();rows.push_back(tmp->val);if(cur == 0){if(tmp->left)  stack[next].push(tmp->left);if(tmp->right)  stack[next].push(tmp->right);}else{if(tmp->right)  stack[next].push(tmp->right);if(tmp->left)  stack[next].push(tmp->left);}if(stack[cur].empty()){cur = next;next = 1-cur;result.push_back(rows);rows.clear();}}return result;}
};

 

本文标签： leetcode102，103Binary Tree Level Order TraversalBinary Tree Zigzag Level Order Traversal

版权声明：本文标题：leetcode【102，103】Binary Tree Level Order TraversalBinary Tree Zigzag Level Order Traversal 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693691119a237126.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。