纯C手撕leetcode-基本算法-BFS

数的深度-广度优先-关键数据结构-fifo

1. 将第一层的节点push 进fifo 中；
2. 初始化当前深度为1， 当前层的size；
3. LOOP 处理
   (0) 树的下一层node 个数nextLevelSize;
   (1)pop出fifo当前层size个元素;
   (2)对fifo当前层pop出来的每个node 的left node, right node push 进fifo，并统计个数，得到树的下一层node个数nextLevelSize；
   (3)当前层深度+1;
   (4)初始化curLevelSize = nextLevelSize;

树的最大深度- C语言实现

#define MAXSIZE (10000)
int maxDepth(struct TreeNode* root){
    //fifo
    if(root == NULL)
        return 0;
    
    struct TreeNode **fifo=malloc(sizeof(struct TreeNode *) * MAXSIZE);
    int head = 0, tail = 0;
    int curLevelSize = 0;
    int depth = 0;
    fifo[tail++] = root;
    curLevelSize++;
    while(head < tail) {
        int nextLevelSize = 0;
        int i;
        int pass = 0;
        for(i=0;i<curLevelSize;i++){
            struct TreeNode *node = fifo[head++];

            if(node->left) {
                fifo[tail++]= node->left;
                nextLevelSize++;
            } 

            if(node->right) {
                fifo[tail++]= node->right;
                nextLevelSize++;
            } 
                
        }


        depth++;
        curLevelSize = nextLevelSize;
    }

    return depth;
}

树的最小深度C语言实现，提前跳出循环，其中一个孩子节点为NULL，则跳出。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAXSIZE (100000)

int minDepth(struct TreeNode* root){

    //fifo
    if(root == NULL)
        return 0;
    
    struct TreeNode **fifo=malloc(sizeof(struct TreeNode *) * MAXSIZE);
    int head = 0, tail = 0;
    int curLevelSize = 0;
    int depth = 0;
    fifo[tail++] = root;
    curLevelSize++;
    while(head < tail) {
        int nextLevelSize = 0;
        int i;
        int pass = 0;
        for(i=0;i<curLevelSize;i++){
            struct TreeNode *node = fifo[head++];

            if(node->left) {
                fifo[tail++]= node->left;
                nextLevelSize++;
            } 

            if(node->right) {
                fifo[tail++]= node->right;
                nextLevelSize++;
            } 

            if(NULL == node->left && NULL == node->right) {
                pass =1;
                break;
            }
                
        }

        depth++;
        curLevelSize = nextLevelSize;
        if (pass)
            break;
    }

    return depth;
}