Leetcode:107.二叉树的层次遍历
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为：
[ [15,7], [9,20], [3] ]
解题思路：
二叉树的层次遍历+反序输出。层次遍历请参考Leetcode:102.二叉树的层次遍历。
https://blog.****.net/qq_23523409/article/details/83720425
| #define hasLChild(x) (!(x->left==NULL)) #define hasRChild(x) (!(x->right==NULL)) class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> res = levelOrder(root); for (int i = 1; i <= int(res.size())/2; i++) { swap(res[i - 1], res[int(res.size()) - i]); } return res; } vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if (root == NULL) return res; queue<TreeNode*> Q; TreeNode* node; vector<int> res1; Q.push(root); while (!Q.empty()) { int size = Q.size(); res1.clear(); for (int i = 1; i <= size; i++) { node = Q.front(); res1.push_back(node->val); if (hasLChild(node)) { Q.push(node->left); } if (hasRChild(node)) { Q.push(node->right); } Q.pop(); } res.push_back(res1); } return res; } }; TreeNode* Int2Tree(vector<int> data) { TreeNode* root; int size = data.size(), pos = 1; if (size == 0) root = NULL; root = new TreeNode(data[0]); queue<TreeNode*> Q; TreeNode* temp; Q.push(root); while (pos < size) { if (!Q.empty()) { temp = Q.front(); if (data[pos] != NULL) { temp->left = new TreeNode(data[pos]); Q.push(temp->left); } if ((pos + 1 < size) && data[pos + 1] != NULL) { temp->right = new TreeNode(data[pos + 1]); Q.push(temp->right); } Q.pop(); } pos += 2; } return root; } |