题目
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
