leetcode做题笔记107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路一：递归+调换顺序

int** levelOrderBottom(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {int** levelOrder = malloc(sizeof(int*) * 2001);*returnColumnSizes = malloc(sizeof(int) * 2001);*returnSize = 0;if (!root) {return levelOrder;}struct TreeNode** q = malloc(sizeof(struct TreeNode*) * 2001);int left = 0, right = 0;q[right++] = root;while (left < right) {int len = right - left;int* level = malloc(sizeof(int) * len);(*returnColumnSizes)[*returnSize] = len;for (int i = 0; i < len; ++i) {struct TreeNode* node = q[left++];level[i] = node->val;if (node->left != NULL) {q[right++] = node->left;}if (node->right != NULL) {q[right++] = node->right;}}levelOrder[(*returnSize)++] = level;}for (int i = 0; 2 * i < *returnSize; ++i) {int* tmp1 = levelOrder[i];levelOrder[i] = levelOrder[(*returnSize) - i - 1];levelOrder[(*returnSize) - i - 1] = tmp1;int tmp2 = (*returnColumnSizes)[i];(*returnColumnSizes)[i] = (*returnColumnSizes)[(*returnSize) - i - 1];(*returnColumnSizes)[(*returnSize) - i - 1] = tmp2;}return levelOrder;
}

分析：

本题要求二叉树的层序遍历，并且是从下至上的层序遍历，可以考虑先按照从上至下的层序遍历先将层序遍历结果放到数组中，再对每层的顺序进行交换，即利用tmp1存储每层数据以中间数为分界线交换不同层的数，最后输出levelOrder

总结：

本题考察二叉树层序遍历，为该类题目的变式，将排好序的二叉树调换顺序即可做出