代码随想录算法训练营第十二天|Day12二叉树

递归遍历 

题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html

思路

每次写递归，按照三要素来写，可以写出正确的递归算法！

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

void preOrder(struct TreeNode* root, int* ret, int* returnSize) {
    if(root == NULL)
        return;
    ret[(*returnSize)++] = root->val;
    preOrder(root->left, ret, returnSize);
    preOrder(root->right, ret, returnSize);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    preOrder(root, ret, returnSize);
    return ret;
}
void inOrder(struct TreeNode* node, int* ret, int* returnSize) {
    if(!node)
        return;
    inOrder(node->left, ret, returnSize);
    ret[(*returnSize)++] = node->val;
    inOrder(node->right, ret, returnSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    inOrder(root, ret, returnSize);
    return ret;
}
void postOrder(struct TreeNode* node, int* ret, int* returnSize) {
    if(node == NULL) 
        return;
    postOrder(node->left, ret, returnSize);
    postOrder(node->right, ret, returnSize);
    ret[(*returnSize)++] = node->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret= (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    postOrder(root, ret, returnSize);
    return ret;
}

学习反思 

之前写递归的时候总是有问题，用这三步之后感觉清晰了很多

迭代遍历

题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html

思路

typedef struct TreeNode {  
    int val;  
    struct TreeNode *left;  
    struct TreeNode *right;  
} TreeNode;  
TreeNode* createNode(int val) {  
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));  
    newNode->val = val;  
    newNode->left = NULL;  
    newNode->right = NULL;  
    return newNode;  
}    
void postorderTraversal(TreeNode* root, int* result, int* returnSize) {  
    TreeNode* stack[1000];
    int top = -1; 
    int index = 0; 
  
    if (root == NULL) {  
        *returnSize = 0;  
        return;  
    }    
    stack[++top] = root;  
    while (top != -1) {  
        TreeNode* node = stack[top--];  
        result[index++] = node->val;  
        if (node->right) {  
            stack[++top] = node->right;  
        }  
        if (node->left) {  
            stack[++top] = node->left;  
        }  
    }  
    for (int i = 0; i < index / 2; i++) {  
        int temp = result[i];  
        result[i] = result[index - i - 1];  
        result[index - i - 1] = temp;  
    }    
    *returnSize = index;  
}  

学习反思 

感觉有些困难，需要多理解。

层序遍历

题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

思路

 typedef struct TreeNode {  
    int val;  
    struct TreeNode *left;  
    struct TreeNode *right;  
} TreeNode;   
typedef struct QueueNode {  
    TreeNode *treeNode;  
    struct QueueNode *next;  
} QueueNode;   
typedef struct Queue {  
    QueueNode *front;  
    QueueNode *rear;  
} Queue;   
Queue* createQueue() {  
    Queue *q = (Queue*)malloc(sizeof(Queue));  
    q->front = q->rear = NULL;  
    return q;  
}   
void enqueue(Queue *q, TreeNode *node) {  
    QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));  
    newNode->treeNode = node;  
    newNode->next = NULL;  
    if (q->rear == NULL) {  
        q->front = q->rear = newNode;  
    } else {  
        q->rear->next = newNode;  
        q->rear = newNode;  
    }  
}      
TreeNode* dequeue(Queue *q) {  
    if (q->front == NULL) return NULL;  
    QueueNode *temp = q->front;  
    TreeNode *node = temp->treeNode;  
    q->front = q->front->next;  
    if (q->front == NULL) q->rear = NULL;  
    free(temp);  
    return node;  
}  
int isEmpty(Queue *q) {  
    return q->front == NULL;  
}  
int** levelOrder(TreeNode* root, int* returnSize, int** returnColumnSizes) {  
    Queue *que = createQueue();  
    if (root != NULL) enqueue(que, root);   
    int **result = NULL;  
    *returnColumnSizes = NULL;  
    *returnSize = 0;  
    while (!isEmpty(que)) {  
        int size = isEmpty(que) ? 0 : 1; 
        QueueNode *current = que->front;   
        while (current->next != NULL) {  
            size++;  
            current = current->next;  
        }  
        result = (int**)realloc(result, (*returnSize + 1) * sizeof(int*));  
        result[*returnSize] = (int*)malloc(size * sizeof(int));  
        (*returnColumnSizes) = (int*)realloc((*returnColumnSizes), (*returnSize + 1) * sizeof(int));  
        (*returnColumnSizes)[*returnSize] = size;  
        for (int i = 0; i < size; i++) {  
            TreeNode *node = dequeue(que);  
            result[*returnSize][i] = node->val;  
            if (node->left) enqueue(que, node->left);  
            if (node->right) enqueue(que, node->right);  
        }  
        (*returnSize)++;  
    }    
    return result;  
}  

学习反思

感觉有些困难，需要多理解。

总结

对二叉树和递归有了深刻认识，加油！！！