每日一道算法题 LCR 150. 彩灯装饰记录 II

题目

LCR 150. 彩灯装饰记录 II - 力扣（LeetCode）

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans=[]
        if not root:
            return ans
        qu=[root]
        while qu:
            le=len(qu)
            row=[]
            for _ in range(le):
                cur=qu.pop(0)
                row.append(cur.val)
                if cur.left:
                    qu.append(cur.left)
                if cur.right:
                    qu.append(cur.right)
            ans.append(row)
        return ans

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 #include <queue>
class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) 
    {
        vector<vector<int>> ans;
        queue<TreeNode*> qu;
        if(root!=NULL)  qu.push(root);

        while(!qu.empty())
        {
            int le=qu.size();
            vector<int> row;
            for(int _=0;_<le;_++)
            {
                TreeNode* cur=qu.front();
                qu.pop();
                row.push_back(cur->val);
                if(cur->left) qu.push(cur->left);
                if(cur->right) qu.push(cur->right);
            }
            ans.push_back(row);
        }

    return ans;
    }
};

C语言

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** decorateRecord(struct TreeNode* root, int* returnSize,int** returnColumnSizes) 
{
    if (root == NULL) {
        *returnSize = 0;
        return root;
    }

    struct TreeNode* qu[1100];
    struct TreeNode* cur;
    int front = 0, rear = 0, row = 0, col = 0, next_row_count = 0, cur_row_count = 1;
    int** ans = (int**)malloc(sizeof(int*) * 1100);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 1100);
    qu[rear++] = root;  //入队
    ans[row] = (int*)malloc(sizeof(int) * cur_row_count);
    (*returnColumnSizes)[row] = cur_row_count;
    while (front < rear) {
        cur = qu[front++];  //出队
        ans[row][col++] = cur->val;
        if (cur->left) {
            qu[rear++] = cur->left;
            next_row_count++;
        }
        if (cur->right) {
            qu[rear++] = cur->right;
            next_row_count++;
        }
        cur_row_count--;
        if (cur_row_count == 0) {
            cur_row_count = next_row_count;
            next_row_count = 0;
            col = 0;
            row++;
            ans[row] = (int*)malloc(sizeof(int) * cur_row_count);
            (*returnColumnSizes)[row] = cur_row_count;
        }
    }
    *returnSize = row;
    return ans;
}