LeetCode 107. Binary Tree Level

题目

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

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

 3
 / \
9 20
    / \
  15 7

return its bottom-up level order traversal as:

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

解析

据上请核实Stack和Queue的两篇简书，从普通意义上讲，这就是一道简单的按层次遍历的逆序题目，使用C++或java中自带的数据结构，这道题解决很简单，使用C语言就需要注意细节。
下面模拟一下简单的过程。

a. 3入队
Queue: 3
b. 计算queuesize为1，1入CountStack
CountStack: 1
c. 3出队，并检查3的左子树结点和右子树结点是否为空，不为空则入队
Queue: 9 20
d. 结点3的value入队ValueStack
ValueStack: 3
继续轮询bcd三步，直至队列为空。

该轮循环后，queue为空，CountStack和Value分别记录了每层结点数目和每层结点的值。

结果：
CountStack: 1 2 2
ValueStack: 3 9 20 15 7

下面从后往前对每次进行拆分。在这里，栈有个好处，即先进后出，这样对CountStack，pop出来的结点首先输出，即为逆序。取ValueStack时，同样pop出的value从数组后往前赋值。这样循环至CountStack为空，便得到结果。

代码（C语言）

首先是Stack的实现

// Stack.h
#ifndef Stack_h
#define Stack_h

#include <stdbool.h>

#define STACK_INITSIZE          1000
#define STACK_INCRESIZE         100

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

typedef struct TreeNodeStack {
    struct TreeNode** base;
    
    int top;
    int size;
} TreeNodeStack;

TreeNodeStack* createStack(void);
bool enlargeStack(TreeNodeStack* stack);
bool pushStack(TreeNodeStack* stack, struct TreeNode* node);
struct TreeNode* popStack(TreeNodeStack* stack);
int sizeOfStack(TreeNodeStack* stack);
bool isStackEmpty(TreeNodeStack* stack);
void destroyStack(TreeNodeStack* stack);

#endif /* Stack_h */


// Stack.c
#include "Stack.h"
#include <malloc/malloc.h>
#include <stdlib.h>

TreeNodeStack* createStack(void) {
    TreeNodeStack* stack = (TreeNodeStack*)malloc(sizeof(TreeNodeStack));
    
    if (!stack)
        return NULL;
    
    stack->base = (struct TreeNode**)malloc(STACK_INITSIZE * sizeof(struct TreeNode*));
    
    if (!stack->base)
        return NULL;
    
    stack->top = 0;
    stack->size = STACK_INITSIZE;
    
    return stack;
}

bool enlargeStack(TreeNodeStack* stack) {
    if (!stack)
        return false;
    
    int newSize = STACK_INITSIZE + STACK_INCRESIZE;
    stack->base = (struct TreeNode**)realloc(stack->base,
                                sizeof(struct TreeNode**) * newSize);
    
    if (!stack->base)
        return false;
    
    stack->size = newSize;
    
    return true;
}

bool pushStack(TreeNodeStack* stack, struct TreeNode* node) {
    if (stack->top >= stack->size) {
        if (!enlargeStack(stack))
            return false;
    }
    
    stack->base[stack->top++] = node;
    
    return true;
}

struct TreeNode* popStack(TreeNodeStack* stack) {
    if (isStackEmpty(stack))
        return NULL;
    
    return stack->base[--stack->top];
}

int sizeOfStack(TreeNodeStack* stack) {
    return stack->top;
}

bool isStackEmpty(TreeNodeStack* stack) {
    return stack->top == 0;
}

void destroyStack(TreeNodeStack* stack) {
    free(stack->base);
    free(stack);
}

其次是Queue的实现

// Queue.h
#ifndef Queue_h
#define Queue_h
#include "Stack.h"

typedef struct StackQueue {
    TreeNodeStack* stack1;
    TreeNodeStack* stack2;
} StackQueue;

StackQueue* createQueue(void);
void destroyQueue(StackQueue* queue);
void enQueue(StackQueue* queue, struct TreeNode* node);
struct TreeNode* deQueue(StackQueue* queue);
bool isQueueEmpty(StackQueue* queue);
int sizeOfQueue(StackQueue* queue);

#endif /* Queue_h */


// Queue.c
#include "Queue.h"
#include <malloc/malloc.h>
#include <stdlib.h>

StackQueue* createQueue(void) {
    StackQueue* queue = (StackQueue*)malloc(sizeof(StackQueue));
    if (!queue)
        return NULL;
    
    queue->stack1 = createStack();
    queue->stack2 = createStack();
    
    return queue;
}

void destroyQueue(StackQueue* queue) {
    destroyStack(queue->stack1);
    destroyStack(queue->stack2);
    
    free(queue);
}

void enQueue(StackQueue* queue, struct TreeNode* node) {
    pushStack(queue->stack1, node);
}

struct TreeNode* deQueue(StackQueue* queue) {
    if (isStackEmpty(queue->stack2)) {
        while (!isStackEmpty(queue->stack1)) {
            struct TreeNode* node = popStack(queue->stack1);
            
            pushStack(queue->stack2, node);
        }
    }
    
    return popStack(queue->stack2);
}

bool isQueueEmpty(StackQueue* queue) {
    return isStackEmpty(queue->stack1) && isStackEmpty(queue->stack2);
}

int sizeOfQueue(StackQueue* queue) {
    return sizeOfStack(queue->stack1) + sizeOfStack(queue->stack2);
}

最后是实现逆序的函数

int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize)
{
    if (!root) {
        (* columnSizes) = NULL;
        (* returnSize) = 0;
        
        return NULL;
    }
    
    StackQueue* queue = createQueue();
    
    TreeNodeStack* nodeValueStack = createStack();
    TreeNodeStack* layerCountStack = createStack();
    
    enQueue(queue, root);
    
    int nodesCount = 1;
    struct TreeNode* treeNode = NULL;
    
    while (!isQueueEmpty(queue)) {
        nodesCount = sizeOfQueue(queue);
        
        // count stack
        pushStack(layerCountStack, (struct TreeNode*)(intptr_t)nodesCount);
        
        for (int i = 0; i < nodesCount; ++i) {
            treeNode = deQueue(queue);
            
            if (treeNode->left)
                enQueue(queue, treeNode->left);
            
            if (treeNode->right)
                enQueue(queue, treeNode->right);
            
            pushStack(nodeValueStack, (struct TreeNode*)(intptr_t)treeNode->val);
        }
    }
    
    (* returnSize) = sizeOfStack(layerCountStack);
    (* columnSizes) = (int*)malloc(sizeof(int) * (* returnSize));
    
    int** returnArray = (int**)malloc(sizeof(int*) * (* returnSize));
    int j = 0;
    
    while (!isStackEmpty(layerCountStack)) {
        nodesCount = (int)(intptr_t)popStack(layerCountStack);
        (* columnSizes)[j] = nodesCount;
        
        int* curLayerValueArr = (int*)malloc(sizeof(int) * nodesCount);
        
        for (int i = nodesCount - 1; i >= 0; --i) {
            curLayerValueArr[i] = (int)(intptr_t)popStack(nodeValueStack);
        }
        
        returnArray[j] = curLayerValueArr;
        
        ++j;
    }
    
    destroyStack(layerCountStack);
    destroyStack(nodeValueStack);
    destroyQueue(queue);
    
    return returnArray;
}

代码已提交至github中

https://github.com/njim3/LeetCode107