首页 > 代码库 > leetcode Binary Tree Level Order Traversal II
leetcode Binary Tree Level Order Traversal II
是这题的变种
对一棵树从最后一次开始层次遍历，并返回结果。例如：
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]]
思路：用一个queue遍历每行，行与行之间NULL分开，然后用stack记录每次的结果，最后将stack中的导出：
/** * 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) return ans; queue<TreeNode *> que; stack<vector<int> > sta; vector<int> tmp; TreeNode *p; que.push(root); que.push(NULL); while(!que.empty()) //先把结果放在stack中 { p = que.front(); if (p != NULL) { tmp.push_back(p -> val); if (p -> left) que.push(p -> left); if (p -> right) que.push(p -> right); que.pop(); } else { que.pop(); sta.push(tmp); tmp.clear(); if (!que.empty()) { que.push(NULL); } } } while(!sta.empty()) // 导出结果 { ans.push_back(sta.top()); sta.pop(); } return ans; }};
后面发现其实stack是多此一举了，可以直接输入到ans中，然后最后利用reverse函数将容器反转即可。
/** * 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) return ans; queue<TreeNode *> que; vector<int> tmp; TreeNode *p; que.push(root); que.push(NULL); while(!que.empty()) //先把结果放在stack中 { p = que.front(); if (p != NULL) { tmp.push_back(p -> val); if (p -> left) que.push(p -> left); if (p -> right) que.push(p -> right); que.pop(); } else { que.pop(); ans.push_back(tmp); tmp.clear(); if (!que.empty()) { que.push(NULL); } } } reverse(ans.begin(), ans.end()); return ans; }};
leetcode Binary Tree Level Order Traversal II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。