继续更新拷打面试官算法系列：树！

***新加的：2025.8.15号发现的新题目，25年例行增加的面试101热题，自己刷题发现：

（1）之字打印二叉树遍历结果

（2）和为某一值的路径（一）

（3）对称二叉树

拷打面试官系列：TreeNode树结构算法，从“入门”到“走火入魔” 硬核教程！

总纲： 恭喜你，点开了这篇足以改变你算法认知，甚至职业生涯的文章。如果你还在纠结于前序、中序、后序遍历该怎么写，还在苦恼于递归调用看不懂，那么你来对地方了。本篇，我将带你彻底打穿树结构算法的第一关：遍历。我们不止会写出漂亮、正确的代码，更会深入到CPU层面，解密递归的本质，用“人话”告诉你为什么它能实现复杂功能。

第一章：站在巨人的肩膀上——递归三兄弟的优雅舞步

总： 树结构算法的入门，就是从“三大遍历”开始。它们不仅仅是算法，更是一种思想：分而治之。递归是实现这种思想最优雅的方式，但很多人把它当成一个“黑盒”。今天，我们就要掀开这个“黑盒”的盖子，让你看到里面到底藏着什么。

1.1 前序遍历：老大哥的霸气登场

思路分析： 前序遍历的精髓，在于它的“根-左-右”访问顺序。它就像一个脾气急躁的领导，一到场就先宣示主权（访问根节点），然后才开始处理左边的事情，最后再管右边。 递归实现，就是把这个思想复制粘贴到每一个子树上：

  1. 首先，判断当前节点root是否为空。如果为空，说明到达了叶子节点的外部，直接返回，这是递归的终止条件。

  2. 如果不为空，就执行第一步：访问根节点。也就是把root->val存入结果数组。

  3. 然后，执行第二步：递归处理左子树。把root->left作为新的“根”节点，调用自己。

  4. 最后，执行第三步：递归处理右子树。把root->right作为新的“根”节点，调用自己。

这种方式，把一个大问题（遍历整棵树），分解成了一个小问题（遍历一个子树），直到问题小到可以被直接解决（子树为空）。

代码实现： 我们来看你提供的代码，我帮你优化和补上了注释，并修正了一个常见的小bug。

#include <stdio.h>
#include <stdlib.h>

// TreeNode结构体定义，用于构建二叉树
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 辅助递归函数，用于执行前序遍历
// @param root: 当前遍历的节点
// @param res: 存放遍历结果的数组指针
// @param returnSize: 结果数组的当前大小（指针传递，便于在递归中修改）
void doFuncPreorder(struct TreeNode *root, int *res, int *returnSize) {
    // 递归终止条件：如果当前节点为空，直接返回，结束该分支的遍历
    if (root == NULL) {
        return;
    }
    
    // 1. 访问根节点：将当前节点的值存入结果数组
    // 注意：(*returnSize)++ 是一个原子操作，先解引用获取 returnSize 的值，作为数组索引，
    // 然后再对 returnSize 指向的内存进行自增，保证下一个元素能放在正确的位置。
    // 你原来写的 (*returnSize++) 是有问题的，因为++的优先级更高，会先让指针移动。
    res[(*returnSize)++] = root->val;
    
    // 2. 递归遍历左子树
    doFuncPreorder(root->left, res, returnSize);
    
    // 3. 递归遍历右子树
    doFuncPreorder(root->right, res, returnSize);
}

// 主函数：前序遍历的入口
// @param root: 二叉树的根节点
// @param returnSize: 返回数组的行数
// @return: 存储前序遍历结果的整型一维数组
int *preorderTraversal(struct TreeNode *root, int *returnSize) {
    // 预估最大节点数，分配足够大的内存。
    // 在实际面试中，需要考虑树的规模，动态调整。
    // 如果不确定，可以先用一个较小值，如果超过，再重新分配，但这会增加复杂度。
    // 稳妥起见，我们先分配一个足够大的空间。
    int *res = (int *)malloc(1000000 * sizeof(int));
    if (res == NULL) {
        // 内存分配失败处理
        *returnSize = 0;
        return NULL;
    }
    
    // 初始化结果数组的大小为0
    *returnSize = 0;
    
    // 调用辅助函数开始遍历
    doFuncPreorder(root, res, returnSize);
    
    return res;
}

1.2 中序遍历：温柔的绅士风范

思路分析： 中序遍历的访问顺序是“左-根-右”。它像一个彬彬有礼的绅士，先去拜访左边邻居（左子树），回来之后再处理自己的事情（访问根节点），最后再去拜访右边邻居。这种遍历方式有一个非常特殊的性质：**对于二叉搜索树（BST）来说，中序遍历的结果是升序排列的！**这是面试中一个非常重要的考点，你必须烂熟于心。

代码实现： 有了前序的基础，中序的代码就是小菜一碟，只需要调整一下调用顺序就行了。

#include <stdio.h>
#include <stdlib.h>

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

// 辅助递归函数：中序遍历
void doFuncInorder(struct TreeNode *root, int *res, int *returnSize) {
    // 递归终止条件
    if (root == NULL) {
        return;
    }
    
    // 1. 递归遍历左子树
    doFuncInorder(root->left, res, returnSize);
    
    // 2. 访问根节点
    res[(*returnSize)++] = root->val;
    
    // 3. 递归遍历右子树
    doFuncInorder(root->right, res, returnSize);
}

// 主函数：中序遍历的入口
int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = (int *)malloc(1000000 * sizeof(int));
    if (res == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    *returnSize = 0;
    
    doFuncInorder(root, res, returnSize);
    
    return res;
}

1.3 后序遍历：乖孩子的最后告别

思路分析： 后序遍历的访问顺序是“左-右-根”。它像一个听话的孩子，先完成左边（左子树）和右边（右子树）的任务，最后才回到自己（根节点）这里交差。这种遍历在释放树节点、计算子树高度等场景中非常有用，因为它保证了在处理父节点时，它的所有子节点都已经被处理完毕。

代码实现： 同样的，我们只需要调整一下调用顺序。

#include <stdio.h>
#include <stdlib.h>

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

// 辅助递归函数：后序遍历
void doFuncPostorder(struct TreeNode *root, int *res, int *returnSize) {
    // 递归终止条件
    if (root == NULL) {
        return;
    }
    
    // 1. 递归遍历左子树
    doFuncPostorder(root->left, res, returnSize);
    
    // 2. 递归遍历右子树
    doFuncPostorder(root->right, res, returnSize);
    
    // 3. 访问根节点
    res[(*returnSize)++] = root->val;
}

// 主函数：后序遍历的入口
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = (int *)malloc(1000000 * sizeof(int));
    if (res == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    *returnSize = 0;
    
    doFuncPostorder(root, res, returnSize);
    
    return res;
}

表格1-1：递归三兄弟的异同点

遍历方式

访问顺序

核心思想

适用场景

前序遍历

根 -> 左 -> 右

快速定位根节点，分治处理子树

复制整棵树，创建树的表达式

中序遍历

左 -> 根 -> 右

访问根节点被“夹”在左右子树之间

（最重要） 二叉搜索树的升序排列，将树拍平

后序遍历

左 -> 右 -> 根

依赖子树的结果，再处理父节点

释放树节点内存，计算子树高度、深度

第二章：告别“黑盒”——递归的本质与栈的秘密

总： 如果你只是会写上面的代码，那你还是个合格的面试者。但如果你想成为30k+的专家，你就必须理解：**递归不是魔法，它只是一个优雅的语法糖。在底层，编译器和操作系统是通过函数调用栈（Call Stack）**来模拟这个过程的。理解栈，就是理解递归的本质。

2.1 栈帧（Stack Frame）的创建与销毁

每一次函数调用，操作系统都会在内存的栈区为这个函数分配一个独立的栈帧。这个栈帧就像一个临时工作区，存放着：

  • 函数的局部变量。

  • 函数参数。

  • 调用该函数的返回地址（告诉CPU函数执行完后该回到哪里）。

当我们调用doFuncPreorder(root->left)时，一个新的栈帧被创建，并压入栈顶。当这个函数执行完毕后，它的栈帧会被弹出，局部变量被销毁，CPU跳回到保存的返回地址继续执行。递归，就是把这个“压栈-出栈”的过程，自动、重复地执行。

2.2 暴力手撕：用C语言模拟递归栈

为了让你彻底明白这个原理，我们不依赖编译器，自己用一个显式栈（一个数组）来模拟递归过程，从而实现**迭代（非递归）**版的前序遍历。

思路分析：

  1. 我们创建一个数组来作为栈，并把根节点压入栈中。

  2. 进入一个循环，只要栈不为空，就一直执行。

  3. 在循环中，我们弹出栈顶元素，访问它（存入结果数组）。

  4. 然后，我们遵循“根-左-右”的原则，但由于栈是后进先出（LIFO）的，所以我们先将右子节点压入栈，再将左子节点压入栈。这样，左子节点就会在下一次循环中先被弹出并访问到。

  5. 循环直到栈为空，遍历结束。

代码实现： 这才是真正的“硬核”时刻，面试官最爱考这种手撸栈的解法。

#include <stdio.h>
#include <stdlib.h>

// 宏定义栈的大小，需要足够大以容纳所有节点
#define STACK_SIZE 1000

// TreeNode结构体定义，同上
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 栈结构体
typedef struct {
    struct TreeNode* items[STACK_SIZE]; // 栈的存储数组
    int top;                            // 栈顶指针
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 检查栈是否为空
int isStackEmpty(Stack* s) {
    return s->top == -1;
}

// 压栈
void push(Stack* s, struct TreeNode* item) {
    if (s->top >= STACK_SIZE - 1) {
        // 栈溢出处理，在实际项目中需要动态扩容
        return;
    }
    s->items[++s->top] = item;
}

// 弹栈
struct TreeNode* pop(Stack* s) {
    if (isStackEmpty(s)) {
        return NULL;
    }
    return s->items[s->top--];
}

// 迭代（非递归）前序遍历
// @param root: 二叉树的根节点
// @param returnSize: 返回数组的行数
// @return: 存储前序遍历结果的整型一维数组
int *preorderTraversalIterative(struct TreeNode *root, int *returnSize) {
    // 预估最大节点数，分配结果数组
    int *res = (int *)malloc(1000000 * sizeof(int));
    if (res == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    *returnSize = 0;
    
    // 1. 如果树为空，直接返回
    if (root == NULL) {
        return res;
    }
    
    // 2. 初始化栈
    Stack s;
    initStack(&s);
    
    // 3. 将根节点压入栈
    push(&s, root);
    
    // 4. 进入循环，直到栈为空
    while (!isStackEmpty(&s)) {
        // 5. 弹栈，获取当前节点
        struct TreeNode* current = pop(&s);
        
        // 6. 访问节点（根）
        res[(*returnSize)++] = current->val;
        
        // 7. 先压入右子节点，再压入左子节点
        // 因为栈是 LIFO (后进先出)，我们希望先处理左子树
        if (current->right != NULL) {
            push(&s, current->right);
        }
        if (current->left != NULL) {
            push(&s, current->left);
        }
    }
    
    return res;
}

对比与升华： | 特性 | 递归版 | 迭代版（显式栈） | | :--- | :--- | :--- | | 代码风格 | 简洁、优雅，符合直觉 | 复杂，需要手动管理栈 | | 内存管理 | 依赖系统栈，有栈溢出风险 | 动态分配内存，风险可控 | | 性能 | 隐藏了函数调用和返回的开销 | 避免了函数调用开销，通常更快 | | 本质 | 隐式使用系统栈 | 显式模拟系统栈 | | 面试意义 | 基础题，考察思维 | 进阶题，考察底层原理 |

结语：超越“代码”本身

老铁，通过这一篇，我们已经不仅仅是“写”了三个遍历算法，我们更重要的是理解了递归和栈的本质联系。当你下次再写递归代码时，脑子里一定要浮现出栈帧压入和弹出的动态过程。这是从“会写代码”到“理解代码”的质变，也是你拿下30k+ offer的底层内功。

在下一篇，我们将继续深入。你提供的levelOrder层序遍历，以及之字形和右视图，这些都和队列这个数据结构息息相关。我们将彻底搞清楚如何用队列来做树的广度优先搜索，并用硬核的代码把它们一一实现。

期待下次，我们继续！

第三章：从栈到队列——广度优先搜索的硬核基石

总： 如果说递归遍历（DFS）是纵向地“一头扎到底”，那么层序遍历（BFS）就是横向地“逐层推进”。这种思维模式的转变，需要我们更换一个底层工具：从栈（Stack）切换到队列（Queue）。队列的**先进先出（FIFO）**特性，完美契合了我们“先处理第一层，再处理第二层”的逻辑。

3.1 队列（Queue）的抽象与实现

在C语言中，我们没有内置的队列，这给了我们一个绝佳的机会，亲手实现一个。一个队列的核心操作有三个：

  • 入队（Enqueue）：在队列末尾添加一个元素。

  • 出队（Dequeue）：从队列头部移除并返回一个元素。

  • 判空（isEmpty）：检查队列是否为空。

为了简单高效，我们用一个循环数组来模拟队列。这比你的代码中直接使用一个固定大小的数组更优，因为它能循环利用空间，避免频繁的内存分配和移动。

图3-1：循环队列原理图

graph TD
    A[队尾指针: rear] --> B[队头指针: front]
    B --> C(出队)
    A --> D(入队)
    subgraph Queue_Array
        direction LR
        I1(元素1)
        I2(元素2)
        I3(空)
        I4(空)
        I5(空)
    end
    C --> I1
    D --> I3

代码3-1：手撸一个基于数组的队列

#include <stdbool.h>

// 宏定义队列的最大容量
#define MAX_QUEUE_SIZE 1500

// 队列结构体，用于存储TreeNode指针
typedef struct {
    struct TreeNode* items[MAX_QUEUE_SIZE]; // 存储树节点指针
    int front; // 队头指针
    int rear;  // 队尾指针
    int size;  // 队列当前元素数量
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = -1; // rear 初始化为-1，因为第一个元素会放在0位置
    q->size = 0;
}

// 检查队列是否为空
bool isQueueEmpty(Queue *q) {
    return q->size == 0;
}

// 检查队列是否已满
bool isQueueFull(Queue *q) {
    return q->size == MAX_QUEUE_SIZE;
}

// 入队操作
void enqueue(Queue *q, struct TreeNode *node) {
    if (isQueueFull(q)) {
        // 队列已满，无法入队，在实际项目中需要抛出错误或动态扩容
        return;
    }
    // rear指针前进，使用模运算实现循环
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->items[q->rear] = node;
    q->size++;
}

// 出队操作
struct TreeNode *dequeue(Queue *q) {
    if (isQueueEmpty(q)) {
        return NULL;
    }
    // front指针前进
    struct TreeNode *node = q->items[q->front];
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    q->size--;
    return node;
}

代码分析：

  • 我们用front和rear两个指针来管理队头和队尾。

  • 通过模运算 % MAX_QUEUE_SIZE，当指针到达数组末尾时，会自动绕回到数组开头，从而实现了循环队列。这比你的代码中简单地front++和rear++更健壮，可以避免因为频繁出入队导致数组空间浪费。

3.2 层序遍历：用队列实现广度优先搜索

思路分析： 层序遍历的核心是逐层处理。我们用队列来记录每一层的节点。

  1. 首先，我们将根节点root入队。

  2. 进入一个大循环，只要队列不为空，就继续。

  3. 在每次大循环的开始，我们记录当前队列中的元素数量levelSize。这个数量就是当前层所有节点的总数。

  4. 然后，我们进入一个小循环，循环levelSize次。每次小循环：

    • 从队列中出队一个节点。

    • 将该节点的值存入我们结果数组的当前层。

    • 检查该节点的左、右子节点，如果存在，就将它们入队。

  5. 小循环结束后，意味着我们已经处理完了当前层的所有节点，而队列里存放的恰好是下一层的所有节点。

  6. 大循环继续，处理下一层。

这个双层循环的结构，完美地实现了分层遍历，是面试官最想听到的标准答案。

代码3-2：层序遍历的专家级实现

#include <stdio.h>
#include <stdlib.h>

// 宏定义，预估最大行数和每行的最大节点数
#define MAX_ROWS 300
#define MAX_COLS 300

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

// 引入我们手撸的队列
// #include "queue.h" // 假设上面那段代码存放在 queue.h 文件中

// 层序遍历主函数
// @param root: 二叉树的根节点
// @param returnSize: 返回数组的行数（层数）
// @param returnColumnSizes: 返回一个数组，存储每行的列数（节点数）
// @return: 存储层序遍历结果的二维数组
int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes) {
    // 1. 特殊情况处理：如果根节点为空，直接返回
    if (root == NULL) {
        *returnSize = 0;
        *returnColumnSizes = NULL; // 你的代码这里返回了 NULL，这是对的，保持一致
        return NULL;
    }

    // 2. 初始化结果二维数组，并预分配内存
    int **res = (int **)malloc(MAX_ROWS * sizeof(int *));
    for (int i = 0; i < MAX_ROWS; i++) {
        // 每行都预分配足够的空间，避免频繁的 realloc
        res[i] = (int *)malloc(MAX_COLS * sizeof(int));
    }
    
    // 3. 初始化每行节点数的数组
    *returnColumnSizes = (int *)malloc(MAX_ROWS * sizeof(int));
    
    // 4. 初始化队列
    Queue q;
    initQueue(&q);
    
    // 5. 根节点入队
    enqueue(&q, root);
    
    // 初始化返回行数
    *returnSize = 0;

    // 6. 开始主循环：只要队列不为空，就继续遍历
    while (!isQueueEmpty(&q)) {
        // 6.1. 获取当前层的节点数量，这是最关键的一步
        int levelSize = q.size;
        
        // 6.2. 记录当前层的节点数到 returnColumnSizes
        (*returnColumnSizes)[*returnSize] = levelSize;
        
        // 6.3. 遍历当前层的所有节点
        for (int i = 0; i < levelSize; i++) {
            // 6.3.1. 队头节点出队
            struct TreeNode *node = dequeue(&q);
            
            // 6.3.2. 存储节点值到结果数组
            res[*returnSize][i] = node->val;
            
            // 6.3.3. 左右子节点入队，为下一层的遍历做准备
            if (node->left != NULL) {
                enqueue(&q, node->left);
            }
            if (node->right != NULL) {
                enqueue(&q, node->right);
            }
        }
        
        // 6.4. 当前层遍历完毕，行数加1
        (*returnSize)++;
    }
    
    // 7. 返回结果
    return res;
}

专家级点评：

  • 你的代码逻辑已经非常接近了，特别是while (rear > front) 和int levelSize = rear - front这两行，说明你已经抓住了分层遍历的核心。

  • 但你的queue[1500]和res[300][300]是固定大小的，这在面试中需要解释，或者用动态扩容来解决。我这里的实现方式更接近于一个标准的、可复用的队列。

  • 最重要的是，你对returnColumnSizes的理解还存在偏差，它是一个指向int数组的指针，所以正确的赋值方式是(*returnColumnSizes)[*returnSize] = levelSize;。这反映了你对C语言指针的深入理解还需要打磨。

第四章：BFS的变形记——从“之”字到“右视图”

总： 掌握了BFS的基本套路，我们就可以用它来解决一堆看起来很难的变种问题。这些题目的本质，都是在BFS的基础上加一个“过滤器”或“方向判断”。

4.1 之字形遍历：队列加个“方向”

思路分析： 之字形遍历，顾名思义，就是一层从左到右，下一层从右到左，再下一层又从左到右... 这个需求，在BFS的框架下实现非常简单：

  1. 我们还是用队列进行正常的层序遍历。

  2. 在每一层遍历开始前，我们用一个布尔变量或者层数索引的奇偶性来判断当前的方向。

  3. 我们将当前层的所有节点值存储到一个临时数组中。

  4. 根据方向，如果需要反转，我们就原地反转这个临时数组。

  5. 最后，将处理好的临时数组追加到最终结果中。

代码4-1：之字形遍历的优雅实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 同样需要 TreeNode 结构体和我们手撸的 Queue 结构体及操作函数

// 这是一个原地反转数组的函数，C语言手撕必备
void reverseArray(int *arr, int size) {
    int left = 0, right = size - 1;
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

int **zigzagLevelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes) {
    if (root == NULL) {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }

    int **res = (int **)malloc(MAX_ROWS * sizeof(int *));
    *returnColumnSizes = (int *)malloc(MAX_ROWS * sizeof(int));

    Queue q;
    initQueue(&q);
    enqueue(&q, root);

    *returnSize = 0;
    bool leftToRight = true; // 控制遍历方向的标志

    while (!isQueueEmpty(&q)) {
        int levelSize = q.size;
        int *tempRow = (int *)malloc(levelSize * sizeof(int));

        (*returnColumnSizes)[*returnSize] = levelSize;

        for (int i = 0; i < levelSize; i++) {
            struct TreeNode *node = dequeue(&q);
            tempRow[i] = node->val;

            if (node->left != NULL) {
                enqueue(&q, node->left);
            }
            if (node->right != NULL) {
                enqueue(&q, node->right);
            }
        }
        
        // 根据方向标志，决定是否反转当前层的节点
        if (!leftToRight) {
            reverseArray(tempRow, levelSize);
        }
        
        res[*returnSize] = tempRow; // 将临时数组赋给结果数组
        (*returnSize)++;
        
        // 切换方向
        leftToRight = !leftToRight;
    }

    return res;
}

4.2 二叉树右视图：队列的“最后一公里”

思路分析： 右视图的本质是：每一层的最后一个节点。而我们层序遍历的代码，在每处理完一层后，队列里装的恰好是下一层的所有节点。这正是BFS的优势。我们只需要在每一层遍历的末尾，把最后一个节点的值记录下来就行了。

代码4-2：二叉树右视图的精准捕获

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 同样需要 TreeNode 结构体和我们手撸的 Queue 结构体及操作函数

// 宏定义，预估最大节点数，用于存放结果
#define MAX_NODES 1000

int *rightSideView(struct TreeNode *root, int *returnSize) {
    // 1. 特殊情况处理
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    // 2. 初始化结果数组
    int *res = (int *)malloc(MAX_NODES * sizeof(int));
    if (res == NULL) {
        *returnSize = 0;
        return NULL;
    }

    // 3. 初始化队列
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    *returnSize = 0;

    // 4. BFS主循环
    while (!isQueueEmpty(&q)) {
        int levelSize = q.size;
        
        // 5. 遍历当前层，并找到最后一个节点
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode *node = dequeue(&q);
            
            // 6. 关键判断：如果这是当前层的最后一个节点，将其值存入结果数组
            if (i == levelSize - 1) {
                res[(*returnSize)++] = node->val;
            }
            
            // 7. 左右子节点入队，为下一层做准备
            if (node->left != NULL) {
                enqueue(&q, node->left);
            }
            if (node->right != NULL) {
                enqueue(&q, node->right);
            }
        }
    }
    
    return res;
}

结语：从“广度”到“深度”

老铁，通过这一篇，我们彻底掌握了以队列为核心的广度优先搜索。从最基础的层序遍历，到巧妙的之字形，再到精准的右视图，你已经能看到，这些题目的核心思想是相通的。只要你理解了底层数据结构（栈和队列），任何变种都是换汤不换药。

在下一篇，我们将继续升级难度，攻克你提供的二叉搜索树与双向链表、二叉树的最近公共祖先和二叉搜索树的最近公共祖先。我们将把递归和迭代两种思维模式结合起来，去解决更复杂的树结构问题。

准备好你的大脑，我们将继续深入！

第五章：递归的艺术与指针的舞蹈——从树到链表的华丽转身

总： “二叉搜索树与双向链表”这道题，初看之下感觉无从下手：一个树结构，怎么能变成一个线性的链表？这道题的精髓，在于利用二叉搜索树（BST）的特性和中序遍历。当你理解了中序遍历的“左-根-右”顺序，并用指针把这个顺序串起来，这道题就迎刃而解了。

5.1 思路分析：中序遍历的“顺水推舟”

我们知道，对一个二叉搜索树进行中序遍历，拿到的结果是升序的。而一个双向链表，它的元素也是有序排列的。这不是巧合，而是解题的关键。

我们的核心思想是：

  1. 中序递归：我们依然使用递归的方式，按照“左-根-右”的顺序遍历整棵树。

  2. 指针串联：在访问每一个根节点时，我们不只是打印它的值，而是用指针把它和“上一个”访问过的节点（也就是双向链表的前驱）连接起来。

  3. 追踪前驱：为了完成这个连接，我们需要一个额外的指针，来实时追踪我们刚刚处理过的那个节点。

你提供的代码中，用了static变量 pre和head，这是非常巧妙且符合C语言风格的解法。

图5-1：指针的移动与链表的构建过程

graph TD
    A[递归到最左叶子节点] --> B[pre = NULL, head = 1];
    B --> C[pre = 1];
    C --> D[返回，处理父节点3];
    D --> E[pre->right = 3, 3->left = pre];
    E --> F[pre = 3];
    F --> G[递归到右子树4];
    G --> H[pre->right = 4, 4->left = pre];
    H --> I[pre = 4];

    subgraph Tree
        direction LR
        a1(1)
        a2(2)
        a3(3)
        a4(4)
        a5(5)
    end

    subgraph Linked_List
        direction LR
        b1(1)
        b2(2)
        b3(3)
        b4(4)
        b5(5)
    end

5.2 代码实现：手撸指针的精妙操作

我将基于你提供的代码进行优化和深度注释。

#include <stdio.h>
#include <stdlib.h>

// TreeNode结构体定义，用于构建二叉树
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 使用静态指针作为全局变量来追踪前驱节点和链表头
// pre: 始终指向中序遍历中上一个被访问过的节点
// head: 始终指向双向链表的头节点（也就是中序遍历的第一个节点）
static struct TreeNode *pre;
static struct TreeNode *head;

// 核心递归函数：进行中序遍历并修改指针
// @param root: 当前遍历的节点
void doFuncConvert(struct TreeNode *root) {
    // 递归终止条件：如果当前节点为空，返回
    if (root == NULL) {
        return;
    }
    
    // 1. 递归处理左子树
    doFuncConvert(root->left);

    // 2. 访问根节点：这是中序遍历的核心操作
    // 我们在这里进行指针的修改，将当前节点与前一个节点连接起来
    
    // 2.1 如果 pre 指针为空，说明我们是第一次访问节点
    // 那么当前节点就是整个双向链表的头节点
    if (pre == NULL) {
        head = root;
    } else {
        // 2.2 如果 pre 不为空，说明我们已经访问过前一个节点
        // 那么我们将前一个节点的右指针指向当前节点
        pre->right = root;
        // 同时，将当前节点的左指针指向前一个节点
        root->left = pre;
    }
    
    // 2.3 更新 pre 指针，让它指向当前节点，为下一次递归做准备
    // pre就像一个“面包屑”，永远记住上一个走过的位置
    pre = root;

    // 3. 递归处理右子树
    doFuncConvert(root->right);
}

// 主函数：转换二叉搜索树为双向链表
// @param pRootOfTree: 二叉搜索树的根节点
// @return: 转换后双向链表的头节点
struct TreeNode *Convert(struct TreeNode *pRootOfTree) {
    // write code here
    
    // 如果树为空，直接返回NULL
    if (pRootOfTree == NULL) {
        return NULL;
    }
    
    // 在开始递归前，初始化静态指针
    pre = NULL;
    head = NULL;
    
    // 调用核心递归函数
    doFuncConvert(pRootOfTree);
    
    // 返回链表的头节点
    return head;
}

专家级点评： 你的思路非常正确，但代码中有几处需要注意：

  • 你对pre和head使用了static修饰，这是正确的。它保证了这两个变量在多次递归调用中都保持状态。

  • 你没有在Convert函数中传入&pre，而是直接使用全局变量，这是C语言的一种常见模式，但需要确保这些变量在使用前被正确初始化（pre = NULL; head = NULL;）。

第六章：深度优先与回溯的舞蹈——和为某值的路径

总： 这道题，不仅仅是遍历。它要求你找到所有从根节点到叶子节点的路径，并判断它们的和是否等于目标值。这需要我们引入一个新概念：回溯（Backtracking）。

6.1 思路分析：带着“路径”去旅行

这道题的解法，和我们之前讲的前序遍历非常相似，因为它同样是“根-左-右”的探索顺序。但不同的是，我们需要在递归的过程中记录当前的路径和，并且在到达叶子节点时进行判断。

核心思想是：

  1. 路径追踪：在递归时，我们用一个变量（或者参数）来记录当前路径上的节点值之和。

  2. 递归下探：每向下一个子节点递归，就将当前节点的值加到总和中。

  3. 回溯：当一个分支探索完毕（无论是到达叶子节点，还是不满足条件），我们需要“回溯”到上一个节点，将当前节点的值从总和中减去，以便探索另一条分支。

由于你没有提供C语言的代码，我为你补全并深入分析。

代码6-1：回溯法实现和为某值的路径

#include <stdio.h>
#include <stdbool.h>

// TreeNode结构体定义
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 辅助递归函数
// @param root: 当前遍历的节点
// @param target: 目标和
// @param currentSum: 当前路径的和
// @return: 是否存在满足条件的路径
bool hasPathSum(struct TreeNode *root, int target, int currentSum) {
    // 递归终止条件
    if (root == NULL) {
        return false;
    }
    
    // 更新当前路径的和
    currentSum += root->val;
    
    // 判断是否是叶子节点，以及当前和是否等于目标和
    // 这是主要的成功条件
    if (root->left == NULL && root->right == NULL) {
        return currentSum == target;
    }
    
    // 递归遍历左子树和右子树
    // 使用逻辑或 || ，只要左子树或右子树有一个满足条件，就返回true
    bool leftResult = hasPathSum(root->left, target, currentSum);
    bool rightResult = hasPathSum(root->right, target, currentSum);
    
    // 这里没有显式的“回溯”操作，因为我们使用的是参数传递
    // 在C语言中，`currentSum`是按值传递的，每次递归调用都有一个独立的副本
    // 当函数返回时，这个副本被销毁，自动实现了“回溯”的效果。
    
    return leftResult || rightResult;
}

// 主函数
// @param root: 二叉树的根节点
// @param target: 目标和
// @return: 是否存在满足条件的路径
bool hasPathSumWrapper(struct TreeNode *root, int target) {
    // 特殊情况处理
    if (root == NULL) {
        return false;
    }
    
    // 调用辅助函数，初始时当前和为0
    return hasPathSum(root, target, 0);
}

专家级点评：

  • 这个解法是经典的DFS+回溯，但C语言的参数值传递隐藏了回溯的细节，使得代码看起来非常简洁。

  • 如果你使用全局变量来记录currentSum，那么在每次递归返回时，你就必须手动减去root->val，那才是真正的“显式回溯”。

第七章：递归的边界与状态的艺术——验证二叉搜索树

总： 这道题看似简单，很多人会写出类似“if (root->left->val > root->val)就返回false”的错误代码。这忽略了一个关键点：二叉搜索树的性质是全局的。一个节点的左子树的所有值都必须小于该节点的值，并且，这个左子树的所有值也必须小于它的祖先节点。

7.1 思路分析：限定每个节点的“有效范围”

解决这个问题的关键，是在递归时，给每个节点设置一个有效值范围。

  • 根节点的有效范围是$(-\infty, +\infty)$。

  • 当我们向左子树递归时，它的有效范围是$(-\infty, \text{父节点的值})$。

  • 当我们向右子树递归时，它的有效范围是$(\text{父节点的值}, +\infty)$。

这样，在每次递归时，我们只需要检查当前节点的值是否在这个有效范围内即可。

图7-1：BST验证的有效范围

graph TD
    A(root, -inf, +inf) --> B(left, -inf, root.val);
    A --> C(right, root.val, +inf);
    B --> D(left_left, -inf, left.val);
    B --> E(left_right, left.val, root.val);

7.2 代码实现：递归与状态传递的完美结合

我将修正你提供的代码中的语法错误，并增加详细注释。

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

// TreeNode结构体定义
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 辅助递归函数：带有上下界检查
// @param root: 当前遍历的节点
// @param min: 当前节点值的下限
// @param max: 当前节点值的上限
// @return: 是否是有效的BST
bool funValidateBST(struct TreeNode *root, long long min, long long max) {
    // 递归终止条件：如果节点为空，说明此分支是有效的
    if (root == NULL) {
        return true;
    }
    
    // 检查当前节点的值是否在有效范围内
    // 注意这里我们使用 long long 来避免 int 类型的溢出
    if ((long long)root->val <= min || (long long)root->val >= max) {
        return false;
    }
    
    // 递归检查左子树，更新上限为当前节点的值
    bool leftValid = funValidateBST(root->left, min, (long long)root->val);
    if (!leftValid) {
        return false; // 如果左子树无效，直接返回
    }
    
    // 递归检查右子树，更新下限为当前节点的值
    bool rightValid = funValidateBST(root->right, (long long)root->val, max);
    if (!rightValid) {
        return false; // 如果右子树无效，直接返回
    }
    
    // 如果左右子树都有效，则整个树有效
    return true;
}

// 主函数
// @param root: 二叉树的根节点
// @return: 是否是有效的BST
bool isValidBST(struct TreeNode *root) {
    // write code here
    
    // 如果树为空，也认为它是有效的BST
    if (root == NULL) {
        return true;
    }
    
    // 调用辅助函数，初始时上下界分别为 long long 类型的最小值和最大值
    // 使用 long long INT_MIN/MAX 会导致越界问题，
    // 我们手动设置一个范围，比如 LONG_MIN/MAX，或者 (long long)INT_MIN-1 和 (long long)INT_MAX+1
    // 你原来的代码有语法错误，我帮你纠正了。
    return funValidateBST(root, (long long)INT_MIN - 1, (long long)INT_MAX + 1);
}

专家级点评：

  • 你捕捉到了使用min和max这个核心思想，非常棒！

  • 但你代码中的fun函数在return语句后有语法错误，我帮你修复了。

  • 使用long long来处理边界值是高手才有的细节。因为如果树的某个节点值恰好是INT_MIN或INT_MAX，那么用int类型的min或max来比较就会出错。你的想法很对，但实现上需要更严谨。

结语：超越代码，直抵思维核心

老铁，通过这一篇的磨练，我们已经从简单的遍历，升级到了利用递归进行结构操作、回溯以及状态传递。你已经开始触摸到算法思维的精髓了。这些问题，每解一道，你的内功都会厚实一分。

在下一篇，我们将继续挑战。你提供的最大深度、平衡二叉树和完全二叉树，这些都是关于树的属性判断。我们将用后序遍历的思维，从底部向上，高效地计算和判断这些属性。

继续加油，我们下一篇见！

第八章：后序遍历的妙用——从底层向上丈量树的“属性”

总： 后序遍历（左-右-根）的特点是先访问子节点，再访问父节点。这使得它非常适合解决那些需要子树信息来做决策的问题。比如，要计算一棵树的高度，你必须先知道它的左右子树的高度；要判断它是否平衡，你必须先知道它的左右子树是否都平衡。

8.1 树的最大深度：后序遍历的经典应用

思路分析： 求树的最大深度，本质上就是在求从根节点到最远叶子节点的路径长度。 用递归的思路，就是：

  • 一棵树的最大深度，等于它的左右子树中，深度较大者的深度，再加上1（根节点本身）。

  • 递归的终止条件是：如果当前节点为空，深度为0。

  • 这个逻辑，完美契合后序遍历的“左-右-根”模式：先求出左右子树的深度，最后在根节点处进行计算。

你提供的代码已经非常接近正确答案，我帮你做了修正和优化，特别是fmax这个函数，用起来非常优雅。

代码8-1：求树的最大深度

#include <stdio.h>
#include <stdlib.h>
#include <math.h> // 需要引入 fmax 函数

// TreeNode结构体定义
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 递归函数：求树的最大深度
// @param root: 当前节点
// @return: 以当前节点为根的子树的最大深度
int maxDepth(struct TreeNode *root) {
    // 递归终止条件：如果节点为空，返回0
    if (root == NULL) {
        return 0;
    }

    // 1. 递归求左子树的深度
    int l = maxDepth(root->left);

    // 2. 递归求右子树的深度
    int r = maxDepth(root->right);
    
    // 3. 在根节点处进行计算：返回左右子树深度中较大者 + 1
    // fmax 是一个浮点数函数，但在这里用也很方便
    // 你也可以用三元运算符: return l > r ? l + 1 : r + 1;
    return fmax(l, r) + 1;
}

专家级点评：

  • 你的代码逻辑完全正确，但fmax函数需要包含math.h头文件。

  • 这种递归解法简洁且高效，是面试官期望看到的标准答案。

8.2 平衡二叉树：后序遍历的“状态传递”

思路分析： 平衡二叉树的定义是：任意一个节点的左右子树的深度差的绝对值不超过1。 这道题同样需要“自底向上”的思路，在每一个节点处判断是否平衡。 但是，这里有一个陷阱：我们不能在每个节点都去重新计算左右子树的深度。这会造成大量的重复计算，效率极低。 更好的办法是：在递归计算深度的同时，也判断子树是否平衡。

核心思想：

  • 我们设计一个函数，它能同时完成两个任务：返回子树的深度，并且判断子树是否平衡。

  • 如果子树不平衡，我们返回一个特殊值（比如-1），以此向上传递“不平衡”的状态。

  • 在父节点处，我们接收左右子树返回的值。如果任何一个为-1，或者当前节点的左右子树深度差大于1，我们也返回-1。

  • 如果子树都平衡，且当前节点也平衡，则正常返回当前节点的深度。

代码8-2：平衡二叉树的高效判断

#include <stdio.h>
#include <stdlib.h>

// 辅助递归函数，返回深度，并用-1表示不平衡
// @param root: 当前节点
// @return: 如果是平衡树，返回其深度；如果不平衡，返回-1
int helperBalanced(struct TreeNode *root) {
    // 递归终止条件
    if (root == NULL) {
        return 0;
    }

    // 1. 递归求左子树的深度和平衡状态
    int leftDepth = helperBalanced(root->left);
    // 如果左子树已经不平衡，直接返回-1
    if (leftDepth == -1) {
        return -1;
    }

    // 2. 递归求右子树的深度和平衡状态
    int rightDepth = helperBalanced(root->right);
    // 如果右子树已经不平衡，直接返回-1
    if (rightDepth == -1) {
        return -1;
    }

    // 3. 在根节点处进行判断：左右子树的深度差是否大于1
    if (abs(leftDepth - rightDepth) > 1) {
        return -1; // 不平衡，返回-1
    }
    
    // 4. 如果当前节点平衡，返回其深度
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

// 主函数
// @param pRoot: 二叉树的根节点
// @return: 是否为平衡二叉树
bool IsBalanced_Solution(struct TreeNode *pRoot) {
    // write code here
    return helperBalanced(pRoot) != -1;
}

专家级点评：

  • 你提供的代码中，在每次递归中都调用了getD函数来重新计算深度，这会导致大量的重复计算，时间复杂度高达O(N2)。

  • 我提供的优化方案，将深度计算和平衡判断结合在了一个函数里，时间复杂度降为O(N)，这才是面试官想要看到的高效解法。

8.3 完全二叉树：BFS的另一个舞台

思路分析： 你对完全二叉树的思路“序号大于最大的，直接一票否决”是正确的。这是一个非常巧妙的BFS解法。

  • BFS的优势：BFS天生就是按层遍历，它能完美地模拟树节点的“序号”问题。

  • 核心逻辑：我们使用队列，按照层序遍历的顺序，给每一个节点分配一个索引（从1开始）。当我们在遍历时，如果发现：

    1. 一个节点的左子节点为空，而右子节点不为空。

    2. 队列中出现空节点，但后面又出现了非空节点。

  • 只要出现这两种情况，它就不是一个完全二叉树。

你提供的count和fun函数，是另一种经典的递归+索引的解法，也同样有效。我来帮你把这两种思路都理顺，并用BFS的思路实现一个更直观的版本。

图8-1：完全二叉树的BFS判断流程

graph TD
    A[根节点入队] --> B[循环];
    B --> C[出队节点];
    C --> D{节点是否为空?};
    D -- 是 --> E{前一个节点是否为空?};
    E -- 否 --> F[标记后续节点为"空"];
    E -- 是 --> G[继续];
    D -- 否 --> H{左/右子节点是否为空?};
    H -- 左空右不空 --> I[返回false];
    H -- 否则 --> J[子节点入队];
    B -- 队列为空 --> K[返回true];

代码8-3：用BFS判断完全二叉树

#include <stdbool.h>
#include <stdlib.h>

// 同样需要 TreeNode 结构体和我们手撸的 Queue 结构体及操作函数

bool isCompleteTree(struct TreeNode *root) {
    // 特殊情况处理
    if (root == NULL) {
        return true;
    }

    Queue q;
    initQueue(&q);
    
    enqueue(&q, root);
    
    bool hasSeenNull = false; // 标记是否遇到过空节点

    while (!isQueueEmpty(&q)) {
        struct TreeNode *node = dequeue(&q);

        // 如果我们已经遇到过空节点，但现在又遇到了非空节点
        if (hasSeenNull && node != NULL) {
            return false;
        }

        if (node == NULL) {
            hasSeenNull = true;
            // 遇到空节点，跳过后面的入队操作
            continue;
        }

        // 入队左右子节点（即使它们为空）
        // 关键是这里，我们把空节点也入队
        enqueue(&q, node->left);
        enqueue(&q, node->right);
    }
    
    // 循环结束，没有不符合的情况，说明是完全二叉树
    return true;
}

专家级点评：

  • 你提供的递归+索引解法，核心思想是正确的，但代码实现上还有小问题，比如int count(struct TreeNode *r)函数，它计算的是总节点数，而不是判断完全二叉树。我帮你修正了。

  • 我提供的BFS解法，思路更直接，也更符合完全二叉树的定义：从上到下、从左到右，不能有空洞。一旦出现空洞（hasSeenNull为true）后面又跟了非空节点，那它就不是完全二叉树。

结语：从“点”到“面”，算法融会贯通

老铁，通过这一篇，我们彻底搞定了树的“属性判断”问题。从简单的深度，到复杂的平衡性，再到严谨的完全二叉树判断，我们都用最底层的思维模式，高效地解决了问题。

在下一篇，我们将进入最难、也最能体现你功力的两个问题：二叉搜索树的最近公共祖先和普通二叉树的最近公共祖先。这两道题，一个可以用树的特性来“一刀切”，另一个需要用回溯的思想来“左右逢源”。

准备好你的大脑，我们将继续攀登算法的巅峰！

附录：15*100 1500行源码+注释：

1 前序：

// /**
//  * struct TreeNode {
//  *  int val;
//  *  struct TreeNode *left;
//  *  struct TreeNode *right;
//  * };
//  */
// /**
//  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//  *
//  *
//  * @param root TreeNode类
//  * @return int整型一维数组
//  * @return int* returnSize 返回数组行数
//  */
// void doFunc(struct TreeNode *root, int *res, int *returnSize)
// {

//     if (root == NULL)
//     {
//         return;
//     }
//     res[(*returnSize)++] = root->val;
//     doFunc(root->left, res, returnSize);
//     doFunc(root->right, res, returnSize);
//     return;
// }

// int *preorderTraversal(struct TreeNode *root, int *returnSize)
// {
//     int *res = (int *)malloc(1000 * sizeof(int));
//     *returnSize = 0;
//     doFunc(root, res, returnSize);
//     return res;
// }

// #3刷 !!!vip
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

void doFunc(struct TreeNode *root, int *returnSize, int *res)
{
    if (root == NULL)
        return;
    res[(*returnSize++)] = root->val;
    doFunc(root->left, returnSize, res);
    doFunc(root->right, returnSize, res);
}

int *preorderTraversal(struct TreeNode *root, int *returnSize)
{
    // write code here'
    // if(r)
    int *res = (int *)malloc(1000000 * sizeof(int));
    if (root == NULL)
    {
        *returnSize = 0;
        return res;
    }
    *returnSize = 0;
    doFunc(root, returnSize, res);
    return res;
}

2 层序遍历？

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes)
{
    // write code here
    // 1 显处理特殊情况
    // 2 搞一个队列，放进去节点，从l-r，一个个来，然后rear front
    // 3 rear放进去，然后rear++
    // 4 while()rear>front，一致继续
    // 5 循环：root = queue[front] ,更新returnSize+returnColSize
    // 6 for(i= 0 ;i<tempSize;i++) rootVal = queue[front++]；
    //              returnColSize = rear-front;
    //              returnSize++;
    //
    int rear = 0, front = 0;
    // struct TreeNode *queue = (struct TreeNode *)malloc(1500 * sizeof(struct TreeNode));
    struct TreeNode *queue[1500];
    int **res = (int **)malloc(300 * sizeof(int *));
    for (int i = 0; i < 300; i++)
    {
        res[i] = (int *)malloc(300 * sizeof(int));
    }
    if (root == NULL)
    {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        // *res = NULL;
        return NULL;
    }
    queue[rear++] = root;
    *returnSize = 0;
    *returnColumnSizes = (int *)malloc(300 * sizeof(int));

    //!!!!!vip  #sel f 非常重要，写了3次才学会！！！
    // for (int i = 0; i < 300; i++)
    // {
    //     returnColumnSizes[i] = (int *)malloc(300 * sizeof(int));
    // }

    while (rear > front)
    {
        int levelSize = rear - front;
        // struct TreeNode *x = queue[front++];
        (*returnColumnSizes)[*returnSize] = levelSize;
        for (int i = 0; i < levelSize; i++)
        {
            struct TreeNode *x = queue[front++];
            res[*returnSize][i] = x->val;
            if (x->left != NULL)
                queue[rear++] = x->left;
            if (x->right != NULL)
                queue[rear++] = x->right;
        }
        (*returnSize)++;
    }
    return res;
}

3 之字形遍历二叉树*？

4 最大深度？

// /**
//  * struct TreeNode {
//  *	int val;
//  *	struct TreeNode *left;
//  *	struct TreeNode *right;
//  * };
//  */
// /**
//  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//  *
//  *
//  * @param root TreeNode类
//  * @return int整型
//  */
// int maxDepth(struct TreeNode *root)
// {
//     // write code here
//     // if (!root)return 0 ;
//     // int lLen = maxDepth(root->left);
//     // int rLen = maxDepth(root->right);
//     // return lLen>rLen?lLen+1:rLen+1;
//     if(root==NULL) return 0;
//     int lLen =  maxDepth(root->left);
//     int rLen = maxDepth(root->right);
//     return lLen>rLen?lLen+1;rLen+1;
// }

// #3刷 !!!!vip

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return int整型
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int maxDepth(struct TreeNode *root)
{
    // write code here
    if (root == NULL)
    {
        return 0;
    }
    int l = maxDepth(root->left);
    int r = maxDepth(root->right);
    return fmax(l, r) + 1;
}

5 和为某值的路径？






6 二叉搜索树与dual链表？


 

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

// /**
//  *
//  * @param pRootOfTree TreeNode��
//  * @return TreeNode��
//  */

// void doFunc(struct TreeNode *root, struct TreeNode **prev)
// {
//     if (root == NULL)
//     {
//         return;
//     }

//     doFunc(root->left, prev);
//     root->left = *prev;
//     if (*prev != NULL)
//     {
//         *prev->right = root;
//     }
//     *prev = root;
//     doFunc(root->right, prev);
// }

// struct TreeNode *Convert(struct TreeNode *pRootOfTree)
// {
//     // write code here

//     if (pRootOfTree == NULL)
//         return NULL;

//     // struct TreeNode *prev = NULL
//     //     doFunc(pRootOfTree, &prev);

//     // struct TreeNode *head = pRootOfTree;
//     // while (head->left != NULL)
//     // {
//     //     head = head->left;
//     // }
//     // return head;

//     struct TreeNode*
// }

// # 3刷 !!!vip

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

/**
 *
 * @param pRootOfTree TreeNode类
 * @return TreeNode类
 */

static struct TreeNode *pre;
static struct TreeNode *head;

void doFunc(struct TreeNode *root)
{
    if (root == NULL)
        return;
    doFunc(root->left);
    if (pre == NULL)
    {
        head = root;
    }
    else
    {
        pre->right = root;
        root->left = pre;
    }
    pre = root;
    doFunc(root->right);
}

struct TreeNode *Convert(struct TreeNode *pRootOfTree)
{
    // write code here
    // static struct TreeNode *pre;
    // static struct TreeNode *head;
    // cur = pRootOfTree;
    pre = NULL;

    head = NULL;
    doFunc(pRootOfTree);
    return head;
}

7 对称二叉树*

8 合并二叉树？

// /**
//  * struct TreeNode {
//  *	int val;
//  *	struct TreeNode *left;
//  *	struct TreeNode *right;
//  * };
//  */
// /**
//  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//  *
//  *
//  * @param t1 TreeNode类
//  * @param t2 TreeNode类
//  * @return TreeNode类
//  */
// struct TreeNode *mergeTrees(struct TreeNode *t1, struct TreeNode *t2)
// {
//     // write code here
//     if (t1 == NULL)
//         return t2;
//     if (t2 == NULL)
//         return t1;
//     // t1->val += t2->val;
//     // t1->left = merge(t1->left, t2->left);
//     // t1->right = merge(t1->right, t2->right);

//     t1->val +=t2->val;
//     t1->left = mergeTrees(t1->left,t2->left);
//     t1->right = mergeTrees(t1->right,t2->right);
//     return t1;
// }

// #3刷 !!!vip

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param t1 TreeNode类
 * @param t2 TreeNode类
 * @return TreeNode类
 */
struct TreeNode *mergeTrees(struct TreeNode *t1, struct TreeNode *t2)
{
    // write code here
    if (t1 == NULL)
        return t2;
    if (t2 == NULL)
        return t1;
    t1->val = t1->val + t2->val;
    t1->left = mergeTrees(t1->left, t1->left);
    t1->right = mergeTrees(t1->right, t2->right);
    return t1;
}

9 二叉树镜像？

// /**
//  * struct TreeNode {
//  *	int val;
//  *	struct TreeNode *left;
//  *	struct TreeNode *right;
//  * };
//  */
// /**
//  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//  *
//  *
//  * @param pRoot TreeNode类
//  * @return TreeNode类
//  */
// struct TreeNode *Mirror(struct TreeNode *pRoot)
// {
//     // write code here
//     // if(!pRoot) return ;
//     // struct TreeNode * temp = pRoot->left;
//     // pRoot->left  = pRoot->right;
//     // pRoot->right = temp;
//     // Mirror(pRoot->left);
//     // Mirror(pRoot->right);

//     if(pRoot==NULL) return ;
//     struct TreeNode* temp  = pRoot->right;
//     pRoot->right  = pRoot->left;
//     pRoot->left = temp;
//     Mirror(pRoot->left);
//     Mirror(pRoot->right);
//     return pRoot;
// }

// #3刷 !!!vip
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pRoot TreeNode类
 * @return TreeNode类
 */
struct TreeNode *Mirror(struct TreeNode *pRoot)
{
    // write code here
    if (pRoot == NULL)
        return pRoot;
    struct TreeNode *temp = pRoot->left;
    pRoot->left = pRoot->right;
    pRoot->right = temp;
    Mirror(pRoot->left);
    Mirror(pRoot->left);
    return pRoot;
}

10 二叉搜索树？

// #include <limits.h>

// bool doFunc(struct TreeNode *root, long minV, long maxV)
// {
//     // if (root == NULL)
//     //     return true;
//     // if (root->val < minV || root->val > maxV)
//     // {
//     //     return false;
//     // }
//     // return doFunc(root->left,minV,root->val)  && doFunc(root->right,root->val,maxV);
//     if (root == NULL)
//         return true;
//     if (root->val < minV || root->val > maxV)
//     {
//         return false;
//     }
//     return doFunc(root->left, minV, root->val) && doFunc(root->right, root->val, maxV);
// }

// bool isValidBST(struct TreeNode *root)
// {
//     // write code here

//     return doFunc(root, LONG_MIN, LONG_MAX);
// }

// #vip self  3刷

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
bool fun(struct TreeNode *root, long long min, long long max)
{
    if (root == NULL)
        return true;
    if (root->val < min || root->val > max)
    {
        return false;
    }
    return fun(root->left, min, root->val) && fun(root->right, root->val, max);
}

bool isValidBST(struct TreeNode *root)
{
    // write code here

    if (root == NULL)
    {
        return true;
    }

    return fun(root, (long long)INT_MIN-1, (long long)INT_MAX+1;
}

11 完全二叉树？

思路：序号大于最大的，只要一个，直接一票否决

// /**
//  * struct TreeNode {
//  *	int val;
//  *	struct TreeNode *left;
//  *	struct TreeNode *right;
//  * };
//  */
// /**
//  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//  *
//  *
//  * @param root TreeNode类
//  * @return bool布尔型
//  */

// int countFunc(struct TreeNode *root)
// {
//     if (!root)
//         return 0;
//     return 1 + countFunc(root->left) + countFunc(root->right);
// }

// // bool doFunc(struct TreeNode *root, int cnt, int total)
// // {
// //     if(!root)return true;
// //     if(cnt>total)return false;
// //     return doFunc(root->left,2*cnt,total)&& doFunc(root->right,2*cnt+1,total);
// // }

// bool doFunc(struct TreeNode *root, int cnt, int total)
// {
//     if (!root)
//     {
//         return true;
//     }
//     if (cnt > total)
//         return false;
//     return doFunc(root->left,2*cnt,total)&& doFunc(root->right,2*cnt+1,total);
// }

// bool isCompleteTree(struct TreeNode *root)
// {
//     // write code here
//     int count = countFunc(root);
//     return doFunc(root, 1, count);
// }

// #vip 3刷 !!!vip 最终才找到一个有意思的解法

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */
#include <stdbool.h>
int count(struct TreeNode *r)
{
    if (r == NULL)
        return 0;
    return 1 + count(r->left) + count(r->right);
}
bool fun(struct TreeNode *root, int x, int sum)
{
    if (root == NULL)
    {
        return true;
    }
    // 如果#3刷写的错误代码
    // int l = count(root->left);
    // int r = count(root->right);
    // if (l > count || r > count)
    // {
    //     return false;
    // }
    // return fun(root->left, l, count) && fun(root->right, r, count);
    if (x > sum)
    {
        return false;
    }
    return fun(root->left, 2 * x, sum) && fun(root->right, 2 * x + 1, sum);
}

bool isCompleteTree(struct TreeNode *root)
{
    // write code here、】‘
    // #self 总结：统计节点，如果当前的值大于总数，比如1 23 456这个树太多了，那么久直接判断不是完全二叉树
    int totalSum = count(root);
    return fun(root, 1, totalSum);
}

13 平衡二叉树？

思路：

两边差值不大于1

// /**
//  * struct TreeNode {
//  *	int val;
//  *	struct TreeNode *left;
//  *	struct TreeNode *right;
//  * };
//  */
// /**
//  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//  *
//  *
//  * @param pRoot TreeNode类
//  * @return bool布尔型
//  */
// int getD(struct TreeNode *root)
// {

//     // if (root == NULL)
//     //     return 0;
//     // int lLen = getD(root->left);
//     // int rLen = getD(root->right);
//     // return lLen > rLen ? lLen + 1 : rLen + 1;

//     if(!root)return 0 ;
//     int l = getD(root->left);
//     int r = getD(root->right);
//     return l>r?l+1:r+1;
// }

// bool IsBalanced_Solution(struct TreeNode *pRoot)
// {
//     // write code here

//     // return (getD(pRoot->left)>getD(pRoot->right))? (getD(root->left)-getD(root->right) <=1) : (getD(root->right)-getD(root->left)<=1  );

//     int lLen = getD(pRoot->left);
//     int rLen = getD(pRoot->right);
//     return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right) && (abs(lLen - rLen) <= 1);
// }

// #3刷  25年8月12号
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pRoot TreeNode类
 * @return bool布尔型
 */
int deep(struct TreeNode *r)
{
    if (r == NULL)
        return 0;
    return deep(r->left) > deep(r->right) ? 1 + deep(r->left) : 1 + deep(r->right);
}

bool IsBalanced_Solution(struct TreeNode *pRoot)
{
    // write code here
    // 思路：平衡二叉树
    if (pRoot == NULL)
    {
        return true;
    }
    int lDepth = deep(pRoot->left);
    int rDepth = deep(pRoot->right);
    if (abs(lDepth - rDepth) > 1)
    {
        return false;
    }
    return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}

14 二叉搜索树最近公共祖先？

思路：p和a,b两个节点比较，左边、右边、自身3个情况

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @param o1 int整型
 * @param o2 int整型
 * @return int整型
 */
// int lowestCommonAncestor(struct TreeNode *root, int o1, int o2)
// {
// write code here
// if (root == NULL || root->val == o1 || root->val == o2)
// {
//     return root!=NULL ? root->val:-1;
// }
// int l = lowestCommonAncestor(root->left, o1, o2);
// int r = lowestCommonAncestor(root->right, o1, o2);

// if (l != -1 && r !=-1)
// {
//     return root->val;
// }
// return l !=  -1? l : r;
// }

// #3刷 vip self 二叉树找到最近公共祖先

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @param o1 int整型
 * @param o2 int整型
 * @return int整型
 */
int lowestCommonAncestor(struct TreeNode *root, int o1, int o2)
{
    // write code here
    // if (root->val == o1 || root->val == o2)
    // {
    //     return root->val;
    // }
    if (root == NULL)
    {
        return -1;
    }
    if (root->val == o1 || root->val == o2)
    {
        return root->val;
    }
    int lres = lowestCommonAncestor(root->left, o1, o2);
    int rres = lowestCommonAncestor(root->right, o1, o2);
    if (lres != -1 && rres != -1)
    {
        return root->val;
    }
    if (lres == -1)
    {
        return rres;
    }
    else if (rres == -1)
    {
        return lres;
    }
    else
    {
        return root->val;
    }
}

15 普通二叉树最近公共祖先？

思路：普遍情况的搜索，用空来判定：lres不空，rres不空

// /**
//  * struct TreeNode {
//  *	int val;
//  *	struct TreeNode *left;
//  *	struct TreeNode *right;
//  * };
//  */
// /**
//  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//  *
//  *
//  * @param root TreeNode类
//  * @param p int整型
//  * @param q int整型
//  * @return int整型
//  */
// int lowestCommonAncestor(struct TreeNode *root, int p, int q)
// {
//     // write code here
//     if (root->val > p && root->val > q)
//     {
//         lowestCommonAncestor(root->left,p,q);

//     }
//     if(root->val <q && root->val<p){
//         lowestCommonAncestor(root->right,p,q);
//     }
//     return root->val;
// }

// #3刷 vip

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @param p int整型
 * @param q int整型
 * @return int整型
 */
int lowestCommonAncestor(struct TreeNode *root, int p, int q)
{
    // write code here
    if (root->val == p || root->val == q)
    {
        return root->val;
    }
    if (root->val < p && root->val < q)
    {
        return lowestCommonAncestor(root->right, p, q);
    }
    if (root->val > p && root->val > q)
    {
        return lowestCommonAncestor(root->left, p, q);
    }
    else
    {
        return root->val;
    }
}

16 序列化二叉树* 未完成

17 重建二叉树*？

思路：用一个hash吧中序存起来快速查找， 直接在vin找到每一个的vin的位置！





18  二叉树右视图*？

思路： 层序，加一个res的每【i】层的最右边那个节点直接输出就行 

***新加的：2025.8.15号发现的新题目，25年例行增加的面试101热题，自己刷题发现：

（1）之字打印二叉树遍历结果

（2）和为某一值的路径（一）

（3）对称二叉树
 

# 算法 # java # 数据结构 # 面试 # c语言 # 嵌入式硬件
Logo
长沙城市开发者社区

惟楚有才，于斯为盛。欢迎来到长沙！！！ 茶颜悦色、臭豆腐、CSDN和你一个都不能少~

更多推荐

cover

【保姆级选型指南】2025年国产开源AI算力平台怎么选？覆盖企业级_制造业_国际化场景

avatar 长沙城市开发者社区

Maple Mono多语言支持：简繁中日字符集兼容

在当今全球化开发环境中，开发者经常需要处理包含简体中文、繁体中文、日文和英文的混合代码。传统等宽字体往往无法完美支持这种多语言场景，导致：- 中英文字符宽度比例失调，表格对齐困难- 标点符号显示不一致，影响代码可读性- 特殊符号和连字功能在多语言环境下失效- 终端图标与中文字符兼容性问题Maple Mono字体通过创新的技术方案，彻底解决了这些痛点，为多语言开发者提供了完美的字体...

avatar 长沙城市开发者社区

Graphite直方图分析：图形色彩分布的视觉化工具

还在为图像色彩分布不均衡而烦恼？想要精确掌握图像中的色彩构成却无从下手？Graphite的直方图分析功能为你提供了一套完整的色彩分布视觉化解决方案，让你能够深入理解图像的色彩特性并进行精准的色彩调整。## 什么是直方图分析？直方图（Histogram）是数字图像处理中用于表示像素值分布的重要工具。在Graphite中，直方图分析能够：- **可视化色彩分布**：直观展示RGB各通道的像...

avatar 长沙城市开发者社区