111. Minimum Depth of Binary Tree

tags: Easy、Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.

解法1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int getHeight(struct TreeNode* node, int height) {
    if (node == NULL) {return height;}
    if (node->left == NULL) {return getHeight(node->right, height+1);}
    if (node->right == NULL) {return getHeight(node->left, height+1);}
    int left_h = getHeight(node->left, height + 1);
    int right_h = getHeight(node->right, height + 1);
    return (left_h > right_h) ? right_h : left_h;
}
int minDepth(struct TreeNode* root) {
    return getHeight(root, 0);
}

解法2:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void getMin(struct TreeNode* node, int* min, int depth) {
    if (node) {
        if ((node->left == NULL) && (node->right == NULL)) {
            if (*min > (depth+1)) {
                *min = depth + 1;
            }
        }
        getMin(node->left, min, depth+1);
        getMin(node->right, min, depth+1);
    }
}
int minDepth(struct TreeNode* root) {
    if (!root) {
        return 0;
    }
    int min = INT_MAX;
    getMin(root, &min, 0);
    return min;
}

637. Average of Levels in Binary Tree

tags: Easy、Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

解法1: BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct TreeNode** createQueue (int* front, int* rear, int max_size) {
    struct TreeNode** queue = (struct TreeNode**)malloc(max_size * sizeof(struct TreeNode*));
    *front = *rear = 0;
    return queue;
}

void enqueue (struct TreeNode** queue, int* rear, struct TreeNode* node) {
    queue[(*rear)++] = node;
}

struct TreeNode* dequeue (struct TreeNode** queue, int* front) {
    return queue[(*front)++];
}

void BFS(struct TreeNode* node, double* array, int* returnSize) {
    if (!node) {return;}
    
    int max_size = 10000;
    int front, rear;
    struct TreeNode** queue = createQueue(&front, &rear, max_size);
    enqueue(queue, &rear, node);
    
    while (front < rear) {
        int size = rear - front;
        double sum = 0;

        for (int i = 0; i < size; i++) {
            struct TreeNode* node = dequeue(queue, &front);
            sum += node->val;
            if (node->left) {enqueue(queue, &rear, node->left);}
            if (node->right) {enqueue(queue, &rear, node->right);}
        }
        array[(*returnSize)++] = sum / size;
    }
    free(queue);
}


double* averageOfLevels(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    double* array = (double*)malloc(10000 * sizeof(double));
    BFS(root, array, returnSize);
    return array;
}

解法2: DFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

void getDepth(struct TreeNode* node, int* depth, int* max_depth) {
    if (!node) {return;}
    (*depth)++;

    if (*depth > * max_depth) {
        *max_depth = *depth;
    }
    if (node->left) {
        getDepth(node->left, depth, max_depth);
    }
    if (node->right) {
        getDepth(node->right, depth, max_depth);
    }
    (*depth)--;
}

void sum(struct TreeNode* node, int *depth, int *max_depth, double *avg, int *num) {
    if (!node) {return;}
    (*depth)++;

    avg[(*depth)-1] += (double)node->val;
    num[(*depth)-1]++;

    if (node->left) {
        sum(node->left, depth, max_depth, avg, num);
    }
    if (node->right) {
        sum(node->right, depth, max_depth, avg, num);
    }
    (*depth)--;

}
double* averageOfLevels(struct TreeNode* root, int* returnSize) {
    int depth = 0, max_depth = 0;
    getDepth(root, &depth, &max_depth);

    double* avg = (double*)calloc(max_depth, sizeof(double));
    int *num = (int*)calloc(max_depth, sizeof(int));

    depth = 0;
    sum(root, &depth, &max_depth, avg, num);

    for (int i = 0; i < max_depth; i++) {
        avg[i] = avg[i] / num[i];
    }
    *returnSize = max_depth;
    return avg;
}

590. N-ary Tree Postorder Traversal

tags: Easy、Tree

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

解法:

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     int numChildren;
 *     struct Node** children;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* postTrace(struct Node* node, int *array, int *index) {
    if (node == NULL) {
        return NULL;
    }
    for (int i = 0; i < node->numChildren; i++) {
        postTrace(node->children[i], array, index);
    }
    array[(*index)++] = node->val; 
    return array;
}
int* postorder(struct Node* root, int* returnSize) {
   if (!root) {
    *returnSize = 0;
    return NULL;
   } 
   int* array = (int*)malloc(10000 * sizeof(int));
   int index = 0;
   postTrace(root, array, &index);
   *returnSize = index;
   return array;
}

617. Merge Two Binary Trees

tags: Easy、Tree

You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.

解法1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    if (!root1 && !root2) {
        return NULL;
    }
    struct TreeNode* merge = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (root1 && root2) {
        merge->val = root1->val + root2->val;
    }
    else if (root1 && !root2) {
        merge->val = root1->val;
    }
    else {
        merge->val = root2->val;
    }
    merge->left = mergeTrees(((root1 != NULL) ? root1->left : NULL), 
                   ((root2 != NULL) ? root2->left : NULL));
    merge->right = mergeTrees(((root1 != NULL) ? root1->right : NULL), 
                   ((root2 != NULL) ? root2->right : NULL));
    return merge;
}

解法2:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    if (!root1) {return root2;}
    if (!root2) {return root1;}
    root1->val = root1->val + root2->val;
    root1->left = mergeTrees(root1->left, root2->left);
    root1->right = mergeTrees(root1->right, root2->right);

    return root1;
}