首页 > 代码库 > 【Lintcode】070.Binary Tree Level Order Traversal II
【Lintcode】070.Binary Tree Level Order Traversal II
题目:
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).
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 ()
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode *root) { vector<vector<int>> res; if (root == nullptr) { return res; } vector<int> v; queue<TreeNode*> q; q.push(root); q.push(nullptr); while (!q.empty()) { TreeNode* cur = q.front(); q.pop(); if(cur == nullptr) { res.insert(res.begin(),v); v.clear(); if(!q.empty()) { q.push(nullptr); } continue; } v.push_back(cur->val); if(cur->left != nullptr) { q.push(cur->left); } if(cur->right != nullptr) { q.push(cur->right); } } return res; } };
Solution 1.1 ()
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode *root) { vector<vector<int>> res; if (root == nullptr) { return res; } queue<TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); vector<int> v; for (int i = 0; i < size; ++i) { TreeNode* cur = q.front(); q.pop(); if(cur->left != nullptr) { q.push(cur->left); } if(cur->right != nullptr) { q.push(cur->right); } v.push_back(cur->val); } res.insert(res.begin(),v); } return res; } };
递归
Solution 2 ()
【Lintcode】070.Binary Tree Level Order Traversal II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。