[LeetCode]107 Binary Tree Level Order Traversal II (easy)

原题

层序遍历，从自底向上按层输出。 左→右→中 解法一 : DFS，求出自顶向下的，最后返回时反转一下。

class Solution { public: vector<vector<int>> res; vector<vector<int>> levelOrderBottom(TreeNode *root) { int level = 0; dfs(root, level); reverse(res.begin(), res.end()); return res; } void dfs(TreeNode *root, int level) { if (root == NULL) return; if (level == res.size()) res.push_back({}); dfs(root->left, level + 1); dfs(root->right, level + 1); res[level].push_back(root->val); } };

解法二： BFS

class Solution { public: vector<vector<int>> res; vector<vector<int>> levelOrderBottom(TreeNode *root) { if (root == NULL) return res; int level = 0; queue<TreeNode *> que; que.push(root); while (!que.empty()) { vector<int> cur; int level = que.size(); for (int i = 0; i < level; i++) { TreeNode *temp = que.front(); que.pop(); cur.push_back(temp->val); if (temp->left != NULL) que.push(temp->left); if (temp->right != NULL) que.push(temp->right); } res.insert(res.begin(), cur); } return res; } };

转载于:https://www.cnblogs.com/ruoh3kou/p/9893408.html

相关资源：数据结构—成绩单生成器