leetcode做题笔记107. 二叉树的层序遍历 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode做题笔记107. 二叉树的层序遍历 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

leetcode做题笔记107. 二叉树的层序遍历 II,二叉树,递归,leetcode,笔记,算法

思路一：递归+调换顺序

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;
}