phpstudy集成环境

 首页 > LEETCODE的一个二叉树遍历输出问题

LEETCODE的一个二叉树遍历输出问题

题目 https://leetcode.com/problems/binary-tree-level-order-traversal/
通过队列实现
总是RUNTIME ERROR， 实在看不出哪里错了。

 
 typedef struct TreeNode * ElementType;

struct QueueNode {
    ElementType value;
    struct QueueNode *next;
};

struct Queue {
    struct QueueNode *front;
    struct QueueNode *rear;
    int size;
};

bool queueIsEmpty(struct Queue *q);
void queueMakeEmpty(struct Queue *q);

struct Queue *queueCreate();
void queueDestroy(struct Queue *q);

///入列 放于尾
void queueEnqueue(ElementType value, struct Queue *q);
///从头部出列
void queueDequeue(struct Queue *q);

///取出头部元素
ElementType queueFront(struct Queue *q);
///取出头部元素并出列
ElementType queueFrontAndDequeue(struct Queue *q);

void queuePrint(struct Queue *q);

struct Queue *queueCreate() {
    struct Queue *queue = (struct Queue * )malloc(sizeof(struct Queue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    
    return queue;
}

void queueDestroy(struct Queue *q) {
    if (q == NULL) {
        return;
    }
    
    queueMakeEmpty(q);
    free(q);
}

bool queueIsEmpty(struct Queue *q) {
    return (q->front == NULL && q->rear == NULL);
}
void queueMakeEmpty(struct Queue *q) {
    if (q == NULL) {
        return;
    }
    
    struct QueueNode *node = q->front;
    if (q->front == q->rear) {
        free(q->front);
    } else {
        while (node) {
            struct QueueNode *tmp = node;
            node = node->next;
            free(tmp);
        }
    }
    
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}
void queueEnqueue(ElementType value, struct Queue *q) {
    if (q == NULL) {
        return;
    }
    
    struct QueueNode *node = (struct QueueNode *)malloc(sizeof(struct QueueNode));
    node->value = value;
    if (q->front == NULL && q->rear == NULL) {
        //第一个
        node->next = NULL;
        
        q->front = node;
        q->rear = node;
        
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    
    q->size++;
}

void queueDequeue(struct Queue *q) {
    if (q == NULL) {
        return;
    }
    
    if (queueIsEmpty(q)) {
        return;
    }
    
    if (q->front == q->rear) {
        //只有一个了
        free(q->front);
        q->front = NULL;
        q->rear = NULL;
    } else {
        struct QueueNode *node = q->front;
        q->front = q->front->next;
        free(node);
    }
    
    q->size--;
}

ElementType queueFront(struct Queue *q) {
    if (q == NULL) {
        return 0;
    }
    
    return q->front->value;
}

ElementType queueFrontAndDequeue(struct Queue *q) {
    ElementType front = queueFront(q);
    queueDequeue(q);
    
    return front;
}

void queuePrint(struct Queue *q) {
    printf("=================\n");
    struct QueueNode *node = q->front;

    if (q->size == 0) {
        printf("empty queue\n");
        return;
    }
    
    if (q->front == q->rear) {
        printf("node:  %p, value: %d\n", node, node->value->val);
    } else {
        while (node) {
            printf("node:  %p, value: %d\n", node, node->value->val);
            node = node->next;
            if (node == q->rear) {
                break;
            }
        }
        
        printf("node:  %p, value: %d\n", node, node->value->val);
        
    }
}

int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    if (root->left == NULL &&  root->right == NULL) {
        return 1;
    } else {
        int leftMax =  maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        return 1 + (leftMax > rightMax ? leftMax : rightMax);
    }
}

int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
     if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    int depth = maxDepth(root);
    int **result = (int **)malloc(sizeof(int *) * depth);
    int *eachArraySize = (int *)malloc(sizeof(int) * depth);
    *returnSize = depth;
    
    struct TreeNode *tmpRoot = root;
    struct Queue *queue = queueCreate();
    queueEnqueue(tmpRoot, queue);
    int currentDepth = 0;
    
    do {
        int length = queue->size;
        int *row = malloc(sizeof(int) * length);
        int size = 0;
        struct Queue *subQueue = queueCreate();
        while (!queueIsEmpty(queue)) {
            ElementType node = queueFrontAndDequeue(queue);
            row[size] = node->val;
            size++;
            
            if (node->left) {
                queueEnqueue(node->left, subQueue);
            }
            
            if (node->right) {
                queueEnqueue(node->right, subQueue);
            }
            
            
        }
        
        result[currentDepth] = row;
        eachArraySize[currentDepth] = size;
        currentDepth++;
        size = 0;
        
        int *nextRow = malloc(sizeof(int) * length);
        
        while (!queueIsEmpty(subQueue)) {
            ElementType node = queueFrontAndDequeue(subQueue);
            
            nextRow[size] = node->val;
            size++;
            
            if (node->left) {
                queueEnqueue(node->left, queue);
            }
            
            if (node->right) {
                queueEnqueue(node->right, queue);
            }
        }
        
        result[currentDepth] = nextRow;
        eachArraySize[currentDepth] = size;
        currentDepth++;
        
        queueDestroy(subQueue);
    } while (!queueIsEmpty(queue));
    
    *columnSizes = eachArraySize;
    
    for (int i = 0; i < * returnSize; i++) {
        int *row = result[i];
        
        
        printf("****************\n");
        for (int j = 0; j < eachArraySize[i]; j++) {
            printf("arraysie:%d, row: %d, column = %d, value: %d\n", eachArraySize[i], i, j, row[j]);
        }
    }
    return result;
}

本地的示例程序如下
//

//  main.c
//  TestLeetCode_C
//
//  Created by xuqing on 15/8/14.
//  Copyright (c) 2015年 ethan. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <unistd.h>

#define bool  int
#define true    1
#define false   0

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

struct QueueNode {
    ElementType value;
    struct QueueNode *next;
};

struct Queue {
    struct QueueNode *front;
    struct QueueNode *rear;
    int size;
};

bool queueIsEmpty(struct Queue *q);
void queueMakeEmpty(struct Queue *q);

struct Queue *queueCreate();
void queueDestroy(struct Queue *q);

///入列 放于尾
void queueEnqueue(ElementType value, struct Queue *q);
///从头部出列
void queueDequeue(struct Queue *q);

///取出头部元素
ElementType queueFront(struct Queue *q);
///取出头部元素并出列
ElementType queueFrontAndDequeue(struct Queue *q);

void queuePrint(struct Queue *q);

struct Queue *queueCreate() {
    struct Queue *queue = (struct Queue * )malloc(sizeof(struct Queue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    
    return queue;
}

void queueDestroy(struct Queue *q) {
    if (q == NULL) {
        return;
    }
    
    queueMakeEmpty(q);
    free(q);
}

bool queueIsEmpty(struct Queue *q) {
    return (q->front == NULL && q->rear == NULL);
}
void queueMakeEmpty(struct Queue *q) {
    if (q == NULL) {
        return;
    }
    
    struct QueueNode *node = q->front;
    if (q->front == q->rear) {
        free(q->front);
    } else {
        while (node) {
            struct QueueNode *tmp = node;
            node = node->next;
            free(tmp);
        }
    }
    
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}
void queueEnqueue(ElementType value, struct Queue *q) {
    if (q == NULL) {
        return;
    }
    
    struct QueueNode *node = (struct QueueNode *)malloc(sizeof(struct QueueNode));
    node->value = value;
    if (q->front == NULL && q->rear == NULL) {
        //第一个
        node->next = NULL;
        
        q->front = node;
        q->rear = node;
        
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    
    q->size++;
}

void queueDequeue(struct Queue *q) {
    if (q == NULL) {
        return;
    }
    
    if (queueIsEmpty(q)) {
        return;
    }
    
    if (q->front == q->rear) {
        //只有一个了
        free(q->front);
        q->front = NULL;
        q->rear = NULL;
    } else {
        struct QueueNode *node = q->front;
        q->front = q->front->next;
        free(node);
    }
    
    q->size--;
}

ElementType queueFront(struct Queue *q) {
    if (q == NULL) {
        return 0;
    }
    
    return q->front->value;
}

ElementType queueFrontAndDequeue(struct Queue *q) {
    ElementType front = queueFront(q);
    queueDequeue(q);
    
    return front;
}

void queuePrint(struct Queue *q) {
    printf("=================\n");
    struct QueueNode *node = q->front;
    
    if (q->size == 0) {
        printf("empty queue\n");
        return;
    }
    
    if (q->front == q->rear) {
        printf("node:  %p, value: %d\n", node, node->value->val);
    } else {
        while (node) {
            printf("node:  %p, value: %d\n", node, node->value->val);
            node = node->next;
            if (node == q->rear) {
                break;
            }
        }
        
        printf("node:  %p, value: %d\n", node, node->value->val);
        
    }
}

int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    if (root->left == NULL &&  root->right == NULL) {
        return 1;
    } else {
        int leftMax =  maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        return 1 + (leftMax > rightMax ? leftMax : rightMax);
    }
}

int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    int depth = maxDepth(root);
    int **result = (int **)malloc(sizeof(int *) * depth);
    int *eachArraySize = (int *)malloc(sizeof(int) * depth);
    *returnSize = depth;
    
    struct TreeNode *tmpRoot = root;
    struct Queue *queue = queueCreate();
    queueEnqueue(tmpRoot, queue);
    int currentDepth = 0;
    
    do {
        int length = queue->size;
        int *row = (int *)malloc(sizeof(int) * length);
        int size = 0;
        struct Queue *subQueue = queueCreate();
        while (!queueIsEmpty(queue)) {
            ElementType node = queueFrontAndDequeue(queue);
            row[size] = node->val;
            size++;
            
            if (node->left) {
                queueEnqueue(node->left, subQueue);
            }
            
            if (node->right) {
                queueEnqueue(node->right, subQueue);
            }
            
            
        }
        
        result[currentDepth] = row;
        eachArraySize[currentDepth] = size;
        currentDepth++;
        size = 0;
        
        int *nextRow = (int*)malloc(sizeof(int) * length);
        
        while (!queueIsEmpty(subQueue)) {
            ElementType node = queueFrontAndDequeue(subQueue);
            
            nextRow[size] = node->val;
            size++;
            
            if (node->left) {
                queueEnqueue(node->left, queue);
            }
            
            if (node->right) {
                queueEnqueue(node->right, queue);
            }
        }
        
        result[currentDepth] = nextRow;
        eachArraySize[currentDepth] = size;
        currentDepth++;
        
        queueDestroy(subQueue);
    } while (!queueIsEmpty(queue));
    
    *columnSizes = eachArraySize;
    /*
    for (int i = 0; i < * returnSize; i++) {
        int *row = result[i];
        
        
        printf("****************\n");
        for (int j = 0; j < eachArraySize[i]; j++) {
            printf("arraysie:%d, row: %d, column = %d, value: %d\n", eachArraySize[i], i, j, row[j]);
        }
    }
     */
    return result;
    
    }

    struct TreeNode *createNode(struct TreeNode *left, struct TreeNode *right, int val) {
    struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node->left = left;
    node->right = right;
    node->val = val;
    
    return node;
}

   int main(int argc, const char * argv[]) {
     printf("hello\n");
    struct TreeNode *five = createNode(NULL, NULL, 5);
    struct TreeNode *four = createNode(NULL, NULL, 4);
    struct TreeNode *three = createNode(NULL, NULL, 3);
    struct TreeNode *two = createNode(four, five, 2);
    struct TreeNode *root = createNode(two, three, 1);
    
    //int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize)
    int *columnSize;
    int returnSize;
    int **level = levelOrder(root, &columnSize, &returnSize);
    printf("hello\n");

    for (int i = 0; i < returnSize; i++) {
        int *row = level[i];
        
        
        printf("****************\n");
        for (int j = 0; j < columnSize[i]; j++) {
            printf("arraysie:%d, row: %d, column = %d, value: %d\n", columnSize[i], i, j, row[j]);
        }
        
        free(row);
    }
    
    free(level);
    free(columnSize);
    
    free(five);
    free(four);
    free(three);
    free(two);
    free(root);
    //int **levelOrder = levelOrder(root, &columnSize, &returnSize);
    sleep(10000000);
  
    return 0;
}

没有实际跑, 只是静态的检查, 说错了勿怪.

你的 levelOrder函数里, 最外面的循环, 我抠出来主要的逻辑:

do {
    int length = queue->size;
    int *row = malloc(sizeof(int) * length);
    int size = 0;
    struct Queue *subQueue = queueCreate();
    while (!queueIsEmpty(queue)) {
        ...
    }
    
    result[currentDepth] = row;
    eachArraySize[currentDepth] = size;
    currentDepth++;
    size = 0;
    
    int *nextRow = malloc(sizeof(int) * length);
    
    while (!queueIsEmpty(subQueue)) {
        ElementType node = queueFrontAndDequeue(subQueue);
        
        nextRow[size] = node->val;
        ...
    }
    
    result[currentDepth] = nextRow;
    eachArraySize[currentDepth] = size;
    currentDepth++;
    
    queueDestroy(subQueue);
} while (!queueIsEmpty(queue));

  1. nextRow 的大小为 length, 这个是queue的size吧? 应该是subQueue的长度. 如果subQueue比queue长, 那么就超出 nextRow的分配范围了;

  2. 需不需要考虑subQueue为空的情况? 那样你的nextRow分配一个0长的空间了吧.

更新

我也是在lc上学到的, bsf用一个queue来做. 代码比用两个queue简单易懂. 大致如下, 希望对你有所帮助:

while (!q.empty()) {
    size = q.size();
    while (size-- > 0) {
        elem = q.poll();
        if (elem->left)
            q.offer(elem->left);
        if (elem->right)
            q.offer(elem->right);
    }
}
【热门文章】
【热门文章】