ARTSDecember 9, 2018 at 04:52 AM作者单一鸣2 分钟阅读3 个标签

ARTS #018

ARTS is an activity initiated by 由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.

ARTS 018

This is article 18

Algorihm algorithm question

107. Binary Tree Level Order Traversal II (Binary Tree Level Order Traversal II)

Question Difficulty: Easy

Given a binary tree, return a bottom-up hierarchical traversal of its node values. (That is, traverse from left to right layer by layer from the layer where the leaf node is to the layer where the root node is)

For example: Given a binary tree [3,9,20,null,null,15,7],

Return its bottom-up hierarchical traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Solution

Language: 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 *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    
}

/**

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 *columnSizes array.
Note: Both returned array and columnSizes array must be malloced, assume caller calls free(). / int levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {

}

Method 1

int getLevelOrderBottom(struct TreeNode* root, int*** ArrayRet, int** columnSizes, int length, int level) {
    if (root == NULL) return length;
    int size = length;
    if (level>size - 1) {
        *ArrayRet = realloc(*ArrayRet, sizeof(int*)*(size + 1));
        (*ArrayRet)[level]= calloc(0, sizeof(int));
        *columnSizes = realloc(*columnSizes, sizeof(int)*(size + 1));
        (*columnSizes)[level] = 0;
        size++;
    }
    (*ArrayRet)[level] = realloc((*ArrayRet)[level], sizeof(int)*((*columnSizes)[level] + 1));
    (*ArrayRet)[level][(*columnSizes)[level]] = root->val;
    (*columnSizes)[level] += 1;
    size = getLevelOrderBottom(root->left, ArrayRet, columnSizes, size, level + 1);
    size = getLevelOrderBottom(root->right, ArrayRet, columnSizes, size, level + 1);
    return size;
}
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    int **ArrayRet = calloc(0, sizeof(int *));
    *returnSize = getLevelOrderBottom(root, &ArrayRet, columnSizes, 0, 0);

    //reverse the array
    int **ret = calloc(*returnSize, sizeof(int *));
    for(int i=0;i<*returnSize;i++){
        ret[i]=calloc((* columnSizes)[*returnSize-i-1],sizeof(int));
        memcpy(ret[i],ArrayRet[*returnSize-i-1],sizeof(int)*(* columnSizes)[*returnSize-i-1]);
    }
    int k=0,j=* returnSize-1;
    while(k<j){
        int tmp=(* columnSizes)[k];
        (* columnSizes)[k++]=(* columnSizes)[j];
        (* columnSizes)[j--]=tmp;
    }
    return ret;
}

Method 2, from LeetCode submission record:


int GetdepthofTree(struct TreeNode* root){
    if (!root) return 0;
    int left = GetdepthofTree(root->left);
    int right = GetdepthofTree(root->right);
    if (left > right)
        return left+1;
    else
        return right+1;
}
 
 
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    if (!root){
        return NULL;
    }
    //获取二叉树的深度，最大层数或者说
    int depth = *returnSize = GetdepthofTree(root);
    
    //ret是一个指向一个二维数组的指针，这一块地址是我们自己开辟的，需要malloc
    int** ret = (int**)malloc(depth*sizeof(int*));
    
    //columnSizes是一个指向指针的指针，这个地址已经指定了，就是说这个地址了存放的下一个地址已经确定了，但是下一个地址里存放的还是地址，这个地址任然不确定，那么就需要malloc了
    //*columnSizes是一个指向一个一维数组的指针，数组的大小也是depth
    
    *columnSizes = (int*)malloc(depth*sizeof(int));
    int front = 0, back = 0;
    struct TreeNode* queue[10000];
    queue[back++] = root;
    while (front < back){
        int start = front, end = back;
        (*columnSizes)[--depth] = end - start;
        front = end;
        //开始的时候我们只给了ret的地址，因为ret是一个二维数组的起始地址，但是这个二维数组里面的一维数组的地址并没有确定，就需要malloc来确定
        ret[depth] = (int*)malloc((end - start)*sizeof(int));
        for (int i=start; i<end; i++){
            ret[depth][i-start] = queue[i]->val;
            if (queue[i]->left) queue[back++] = queue[i]->left;
            if (queue[i]->right) queue[back++] = queue[i]->right;
        }
    }
    return ret;
}

Review

See also: Common data structures and algorithms: https://dandan2009.github.io/2018/11/28/data-structures-part3-language-support/

TIPS

A Beginner’s Guide to Coding Graphics Shaders.

https://gamedevelopment.tutsplus.com/series/a-beginners-guide-to-coding-graphics-shaders--cms-834

This series is pretty good. You can check it out as an introductory tutorial on Graphics Shaders.

iOS simulates weak network method:

Use a real device. There is an option under development and a Network Link Conditioner option in the settings of the real device.

Select one of the types of networks to set the network speed

Set the simulator to a weak network environment: Method 1: Go to Apple Developer Center to download Additional Tools for Xcode

Open System Preferences, find Network Link Conditioner, and double-click to open it.

Network Link Conditioners are effective for the entire system, and the speed of ordinary Internet access will also be limited, so when the test is completed, remember to stop the Network Link Conditioner.

Method 2: Charles

Visual learning tools and websites that demarcate several algorithms:

University of San Francisco Data Structures and Algorithms http://hao.jobbole.com/visualizing-algorithms-and-data-structure/

VisuAlgo: Learn algorithms and data structures through animation http://hao.jobbole.com/visualgo/

Algomation: a learning platform for viewing, creating and sharing algorithms http://hao.jobbole.com/algomation/

Algorithm Visualizer: http://algorithm-visualizer.org Algorithm Visualizer has 10.6k+ stars on GitHub: https://github.com/algorithm-visualizer/algorithm-visualizer

Share an English learning website: https://learnamericanenglishonline.com/Red Level/R1 Do.html

FAQ