继续更新拷打面试官算法系列:树!

***新加的: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;
}

代码分析:

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

  • 通过模运算 % 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变量 prehead,这是非常巧妙且符合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;
}

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

  • 你对prehead使用了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);
}

专家级点评:

  • 你捕捉到了使用minmax这个核心思想,非常棒!

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

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

结语:超越代码,直抵思维核心

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

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

继续加油,我们下一篇见!

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

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

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. 队列中出现空节点,但后面又出现了非空节点。

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

你提供的countfun函数,是另一种经典的递归+索引的解法,也同样有效。我来帮你把这两种思路都理顺,并用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解法,思路更直接,也更符合完全二叉树的定义:从上到下、从左到右,不能有空洞。一旦出现空洞(hasSeenNulltrue)后面又跟了非空节点,那它就不是完全二叉树。

结语:从“点”到“面”,算法融会贯通

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

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

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

附录: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)对称二叉树
 

Logo

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

更多推荐