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

标签：right TreeNode struct 随想录 queue 二叉树 left root 第十三天

226.翻转二叉树

题目链接/文章讲解/视频讲解：https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

递归法

struct TreeNode* invertTree(struct TreeNode* root){
    if(!root)
        return NULL;
    struct TreeNode* temp = root->right;
    root->right = root->left;
    root->left = temp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

迭代法

struct TreeNode* invertTree(struct TreeNode* root){
    if(!root)
        return NULL;
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 100);
    int stackTop = 0;
    stack[stackTop++] = root;
    while(stackTop) {
        struct TreeNode* temp = stack[--stackTop];
        struct TreeNode* tempNode = temp->right;
        temp->right = temp->left;
        temp->left = tempNode;
        if(temp->right)
            stack[stackTop++] = temp->right;
        if(temp->left)
            stack[stackTop++] = temp->left;
    }
    return root;
}

学习反思

对二叉树有了更深刻的认知

101. 对称二叉树

题目链接/文章讲解/视频讲解：https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

递归法

int isMirror(struct TreeNode* left, struct TreeNode* right) {
    if (left == NULL && right == NULL) return 1;
    if (left == NULL || right == NULL) return 0;
    return (left->val == right->val) &&
           isMirror(left->left, right->right) &&
           isMirror(left->right, right->left);
}

int isSymmetric(struct TreeNode* root) {
    return isMirror(root, root);
}

迭代

typedef struct {
    struct TreeNode** nodes; // 存储树节点的指针
    int front;
    int back;
    int capacity;
} Queue;
Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->nodes = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    queue->front = 0;
    queue->back = 0;
    queue->capacity = capacity;
    return queue;
}
void enqueue(Queue* queue, struct TreeNode* node) {
    if (queue->back < queue->capacity) {
        queue->nodes[queue->back++] = node;
    }
}
struct TreeNode* dequeue(Queue* queue) {
    return queue->nodes[queue->front++];
}

int isEmpty(Queue* queue) {
    return queue->front == queue->back;
}
void freeQueue(Queue* queue) {
    free(queue->nodes);
    free(queue);
}
int isSymmetric(struct TreeNode* root) {
    if (root == NULL) return 1;

    Queue* queue = createQueue(2000);
    enqueue(queue, root->left);
    enqueue(queue, root->right);

    while (!isEmpty(queue)) {
        struct TreeNode* left = dequeue(queue);
        struct TreeNode* right = dequeue(queue);
        if (left == NULL && right == NULL) continue;
        if (left == NULL || right == NULL) return 0;
        if (left->val != right->val) return 0;
        enqueue(queue, left->left);
        enqueue(queue, right->right);
        enqueue(queue, left->right);
        enqueue(queue, right->left);
    }

    freeQueue(queue);
    return 1;
}

学习反思

对二叉树有了更深刻的认知。

104.二叉树的最大深度

题目链接/文章讲解/视频讲解： https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html

思路

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

递归

int maxDepth(struct TreeNode* root){
    if(!root)
        return 0;
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    int max = left > right ? left : right;
    return max + 1;
}

迭代

int maxDepth(struct TreeNode* root){
    if(!root)
        return 0;
    int depth = 0;
    struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 6000);
    int queueFront = 0;
    int queueEnd = 0;
    queue[queueEnd++] = root;
    int queueSize;
    while(queueSize = queueEnd - queueFront) {
        int i;
        for(i = 0; i < queueSize; i++) {
            struct TreeNode* tempNode = queue[queueFront + i];
            if(tempNode->left)
                queue[queueEnd++] = tempNode->left;
            if(tempNode->right)
                queue[queueEnd++] = tempNode->right;
        }
        queueFront += queueSize;
        depth++;
    }
    return depth;
}

学习反思

对二叉树有了更深刻的认知。

111.二叉树的最小深度

题目链接/文章讲解/视频讲解：https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html

思路

直觉上好像和求最大深度差不多，其实还是差不少的。

本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）

那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离也同样是最小深度。

递归法

int minDepth(struct TreeNode* root) {
    if (root == NULL) return 0;
    if (root->left == NULL) return minDepth(root->right) + 1;
    if (root->right == NULL) return minDepth(root->left) + 1;
    int leftDepth = minDepth(root->left);
    int rightDepth = minDepth(root->right);
    return (leftDepth < rightDepth ? leftDepth : rightDepth) + 1;
}

迭代法

typedef struct {
    struct TreeNode** nodes; 
    int front;
    int back;
    int capacity;
} Queue;
Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->nodes = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    queue->front = 0;
    queue->back = 0;
    queue->capacity = capacity;
    return queue;
}
void enqueue(Queue* queue, struct TreeNode* node) {
    if (queue->back < queue->capacity) {
        queue->nodes[queue->back++] = node;
    }
}
struct TreeNode* dequeue(Queue* queue) {
    return queue->nodes[queue->front++];
}
int isEmpty(Queue* queue) {
    return queue->front == queue->back;
}
void freeQueue(Queue* queue) {
    free(queue->nodes);
    free(queue);
}
int minDepth(struct TreeNode* root) {
    if (root == NULL) return 0;

    Queue* queue = createQueue(1000);
    enqueue(queue, root);
    int depth = 0;
    while (!isEmpty(queue)) {
        int levelSize = queue->back - queue->front;
        depth++;
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* curr = dequeue(queue);
            if (curr->left == NULL && curr->right == NULL) {
                freeQueue(queue);
                return depth;
            }
            if (curr->left) enqueue(queue, curr->left);
            if (curr->right) enqueue(queue, curr->right);
        }
    }

    freeQueue(queue);
    return depth;
}

学习反思

对二叉树有了更深刻的认知。

总结

二叉树相对来说还是比较难，加油！！！

标签：right,TreeNode,struct,随想录,queue,二叉树,left,root,第十三天
From： https://blog.csdn.net/a6666999d/article/details/142884296

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

226.翻转二叉树

思路

学习反思

101. 对称二叉树

思路

学习反思

104.二叉树的最大深度

思路

学习反思

111.二叉树的最小深度

思路

学习反思

总结

相关文章

赞助商

阅读排行