五月集训（第十九天）二叉树

要是能随手写非递归遍历就好了...."要是"？？

题1.144. 二叉树的前序遍历

有*returnSize，还得另建立一个函数来递归

以下为力扣官解....

void preorder(struct TreeNode* root, int* res, int* resSize) {
    if (root == NULL) {
        return;
    }
    res[(*resSize)++] = root->val;
    preorder(root->left, res, resSize);
    preorder(root->right, res, resSize);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 2000);
    *returnSize = 0;
    preorder(root, res, returnSize);
    return res;
}

题2. 94. 二叉树的中序遍历

这就是递归吗？ 8%的5.8%....

void inorder(struct TreeNode* root, int* res, int* resSize) {
    if (root == NULL) {
        return;
    }
    inorder(root->left, res, resSize);
    res[(*resSize)++] = root->val;
    inorder(root->right, res, resSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int* res = malloc(sizeof(int) * 2000);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
}

题3. 145. 二叉树的后序遍历

void postorder(struct TreeNode* root, int* res, int* resSize) {
    if (root == NULL) {
        return;
    }
    postorder(root->left, res, resSize);
    postorder(root->right, res, resSize);
    res[(*resSize)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* res = malloc(sizeof(int) * 2000);
    *returnSize = 0;
    postorder(root, res, returnSize);
    return res;
}

题4.104. 二叉树的最大深度

借助bfs学习一下队列.....

struct QueNode {
    struct TreeNode *p;
    struct QueNode *next;
};

void init(struct QueNode **p, struct TreeNode *t) {
    (*p) = (struct QueNode *)malloc(sizeof(struct QueNode));
    (*p)->p = t;
    (*p)->next = NULL;
}

int maxDepth(struct TreeNode *root) {
    if (root == NULL) return 0;
    struct QueNode *left, *right;
    init(&left, root);
    right = left;
    int ans = 0, sz = 1, tmp = 0;
    while (left != NULL) {
        tmp = 0;
        while (sz > 0) {
            if (left->p->left != NULL) {
                init(&right->next, left->p->left);
                right = right->next;
                tmp++;
            }
            if (left->p->right != NULL) {
                init(&right->next, left->p->right);
                right = right->next;
                tmp++;
            }
            left = left->next;
            sz--;
        }
        sz += tmp;
        ans++;
    }
    return ans;
}