企业官网建设流程全解析

二叉树的常见类型

1. 满二叉树

定义：除叶子节点外，每个节点都有左右两个子节点；所有叶子都在同一层。 特点：深度为k，节点总数\(2^k-1\)。

2. 完全二叉树

定义：除最后一层外，其余每一层节点都满；最后一层节点从左往右连续排列，中间不能有空缺。

满二叉树一定是完全二叉树；完全二叉树不一定是满二叉树。 数组存储二叉树一般用完全二叉树（堆就是完全二叉树）。

3. 二叉搜索树 BST（二叉查找树）

定义：左子树所有节点值 <根节点；右子树所有节点值> 根节点；左右子树也满足 BST 规则。 特点：查找、插入、删除平均\(O(\log n)\)；最坏退化成链表\(O(n)\)。

4. 平衡二叉树 AVL 树

定义：二叉搜索树，任意节点左右子树高度差绝对值 ≤1。 特点：保证平衡，查找稳定\(O(\log n)\)；插入删除会旋转调整。

5. 红黑树（RB-Tree）

定义：一种自平衡二叉搜索树，通过颜色规则维持平衡。 特点：不严格要求高度差，插入删除旋转次数更少；Java TreeMap、C++ map 底层。

6. 线索二叉树

定义：利用二叉树空指针域，存放前驱、后继节点的指针（线索）。 作用：不用栈就能遍历二叉树。

7. 哈夫曼树（最优二叉树）

定义：带权路径长度 WPL 最小的二叉树。 特点：没有度为 1 的节点；用于哈夫曼编码、数据压缩。

8. 二叉堆（大根堆 / 小根堆）

底层是完全二叉树

• 大根堆：父节点 ≥ 子节点
• 小根堆：父节点 ≤ 子节点 用途：优先队列、TopK 问题。

9. 普通二叉树

没有任何约束，任意节点 0/1/2 个子节点，是最基础的二叉树。

C 语言 非递归求二叉树高度（BFS 层序）

#include <stdio.h> #include <stdlib.h> // 二叉树结点定义 typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 队列结点（BFS用） typedef struct QueueNode { TreeNode *data; struct QueueNode *next; } QueueNode; typedef struct Queue { QueueNode *front, *rear; } Queue; // 初始化队列 Queue* initQueue() { Queue *q = (Queue*)malloc(sizeof(Queue)); q->front = q->rear = NULL; return q; } // 入队 void enQueue(Queue *q, TreeNode *node) { QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode)); newNode->data = node; newNode->next = NULL; if(q->rear == NULL) { q->front = q->rear = newNode; } else { q->rear->next = newNode; q->rear = newNode; } } // 出队 TreeNode* deQueue(Queue *q) { if(q->front == NULL) return NULL; QueueNode *temp = q->front; TreeNode *res = temp->data; q->front = q->front->next; if(q->front == NULL) q->rear = NULL; free(temp); return res; } // 判断队列空 int isEmpty(Queue *q) { return q->front == NULL; } // 非递归BFS求树高 int maxDepth(TreeNode* root) { if(root == NULL) return 0; Queue *q = initQueue(); enQueue(q, root); int depth = 0; while(!isEmpty(q)) { int levelSize = 0; // 统计当前层节点个数 QueueNode *p = q->front; while(p != NULL) { levelSize++; p = p->next; } // 遍历当前一层 for(int i = 0; i < levelSize; i++) { TreeNode *cur = deQueue(q); if(cur->left != NULL) enQueue(q, cur->left); if(cur->right != NULL) enQueue(q, cur->right); } depth++; } free(q); return depth; }

方法 2：栈实现 DFS 迭代版（C 语言）

// 栈元素：保存节点+当前深度 typedef struct StackNode { TreeNode *node; int depth; struct StackNode *next; } StackNode; typedef struct Stack { StackNode *top; } Stack; Stack* initStack() { Stack *s = (Stack*)malloc(sizeof(Stack)); s->top = NULL; return s; } void push(Stack *s, TreeNode *node, int d) { StackNode *newNode = (StackNode*)malloc(sizeof(StackNode)); newNode->node = node; newNode->depth = d; newNode->next = s->top; s->top = newNode; } StackNode* pop(Stack *s) { if(s->top == NULL) return NULL; StackNode *temp = s->top; s->top = s->top->next; return temp; } int isStackEmpty(Stack *s) { return s->top == NULL; } int maxDepthDFS(TreeNode* root) { if(root == NULL) return 0; Stack *s = initStack(); push(s, root, 1); int maxD = 0; while(!isStackEmpty(s)) { StackNode *cur = pop(s); if(cur->depth > maxD) maxD = cur->depth; // 先压右，再压左，保证左先访问 if(cur->node->right) push(s, cur->node->right, cur->depth + 1); if(cur->node->left) push(s, cur->node->left, cur->depth + 1); free(cur); } free(s); return maxD; }

考点总结

1. BFS 层序：逐层遍历，每处理完一层深度 + 1；空间最坏 O (n)
2. DFS 栈：栈存储(节点，当前深度)，弹出时更新最大深度
3. 时间复杂度：\(O(n)\)，每个结点访问一次
4. 空树高度 = 0

DFS（迭代栈版）求二叉树高度 核心思想

一句话：用栈模拟递归的调用过程，深度优先一条路走到最深处，记录每一个节点所在的深度，全程维护最大深度。

拆解

1. 递归本质递归求高度：max(左子树高度,右子树高度)+1，递归会一路往下访问，遇到叶子节点才回溯。 递归是系统帮我们压栈、保存当前节点信息；迭代 DFS 就是我们自己手动用栈保存【节点 + 当前深度】。
2. 栈里存什么栈元素不是单纯节点，是一对信息：(当前节点, 该节点的深度)

• 根节点入栈，深度 = 1
• 每次弹出栈顶节点，拿它的深度去更新全局最大深度maxD

1. 入栈顺序（重点！）

先压右孩子，再压左孩子栈是后进先出，所以弹出的时候先访问左子树，再访问右子树，和递归 DFS 顺序保持一致。

1. 遍历逻辑循环直到栈为空：

• 弹出栈顶节点，更新最大深度
• 如果有右孩子：右孩子入栈，深度 + 1
• 如果有左孩子：左孩子入栈，深度 + 1

举个简单例子

1 / \ 2 3

• 压入 (1,1)
• 弹出 (1,1)，maxD=1；压右 (3,2)，压左 (2,2)
• 弹出 (2,2)，maxD=2；2 无孩子
• 弹出 (3,2)，maxD=2；3 无孩子 栈空，返回最大深度 2

和递归对比

• 递归：函数调用栈自动保存上下文
• 迭代 DFS：自己手动维护栈，保存节点和深度，避免递归栈溢出（树很深的时候）

复杂度

• 时间：\(O(n)\)，每个节点只访问一次
• 空间：\(O(n)\)，最坏斜树，栈里面存全部节点

核心思路

原来代码只记录最大深度值；现在要输出到达最大深度的完整路径。 难点：栈只存(节点,深度)不够，还要记录这条路径上前面所有节点。

两种思路：

1. 栈保存：(当前节点，深度，到这个节点的路径数组)（简单直观，适合理解）
2. 回溯思路：用一个全局 / 数组保存当前路径，找到叶子时判断深度，更新最长路径（更省内存，考研常用）

需求：输出任意一条最长路径（二叉树可能有多条最长路径，这里输出第一条找到的）

思路讲解（迭代 DFS 版，沿用刚才的栈框架）

栈元素需要存三样东西：

1. 结点指针
2. 当前结点的深度
3. 到达该结点的路径（存结点值）

流程：

1. 根节点入栈，路径 =[根值]，深度 = 1
2. 弹出栈顶元素
3. 如果是叶子结点：判断深度是不是大于当前记录的最大深度
   • 如果是：更新最大深度，保存这条路径
4. 不是叶子：先压右孩子，再压左孩子（栈后进先出，优先走左分支）
   • 子节点路径 = 当前路径复制一份，追加子节点的值
5. 栈空之后，打印保存好的最长路径

C 完整代码（迭代 DFS，输出最长路径）

#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 栈元素：节点、深度、路径数组、路径长度 typedef struct StackItem { TreeNode *node; int depth; int *path; // 保存路径值 int pathLen; struct StackItem *next; } StackItem; typedef struct Stack { StackItem *top; } Stack; Stack* initStack() { Stack *s = (Stack*)malloc(sizeof(Stack)); s->top = NULL; return s; } void push(Stack *s, TreeNode *node, int d, int oldPath[], int oldLen) { StackItem *newItem = (StackItem*)malloc(sizeof(StackItem)); newItem->node = node; newItem->depth = d; newItem->pathLen = oldLen + 1; newItem->path = (int*)malloc(sizeof(int) * newItem->pathLen); // 复制旧路径 for(int i = 0; i < oldLen; i++) { newItem->path[i] = oldPath[i]; } newItem->path[oldLen] = node->val; newItem->next = s->top; s->top = newItem; } StackItem* pop(Stack *s) { if(s->top == NULL) return NULL; StackItem *tmp = s->top; s->top = s->top->next; return tmp; } int isStackEmpty(Stack *s) { return s->top == NULL; } // 求最长深度+最长路径 void getLongestPath(TreeNode* root, int *maxDepth, int **resultPath, int *resLen) { *maxDepth = 0; *resultPath = NULL; *resLen = 0; if(root == NULL) return; Stack *s = initStack(); // 根节点路径 int rootPath[1]; rootPath[0] = root->val; push(s, root, 1, rootPath, 0); while(!isStackEmpty(s)) { StackItem *cur = pop(s); TreeNode *p = cur->node; // 叶子结点，判断是否是更长路径 if(p->left == NULL && p->right == NULL) { if(cur->depth > *maxDepth) { *maxDepth = cur->depth; // 释放旧结果 if(*resultPath) free(*resultPath); *resLen = cur->pathLen; *resultPath = (int*)malloc(sizeof(int)*(*resLen)); for(int i = 0; i < *resLen; i++) { (*resultPath)[i] = cur->path[i]; } } } // 先压右，再压左，优先遍历左子树 if(p->right) { push(s, p->right, cur->depth+1, cur->path, cur->pathLen); } if(p->left) { push(s, p->left, cur->depth+1, cur->path, cur->pathLen); } free(cur->path); free(cur); } free(s); } // 新建节点 TreeNode* createNode(int v) { TreeNode *n = (TreeNode*)malloc(sizeof(TreeNode)); n->val = v; n->left = n->right = NULL; return n; } int main(void) { // 构造样例树 /* 1 / \ 2 3 / 4 */ TreeNode *root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); int maxDep; int *path; int pathLen; getLongestPath(root, &maxDep, &path, &pathLen); printf("最大深度 = %d\n", maxDep); printf("最长路径："); for(int i = 0; i < pathLen; i++) { printf("%d ", path[i]); } printf("\n"); free(path); return 0; }

输出：

最大深度 = 3 最长路径：1 2 4

更推荐：递归回溯版本（代码短，写题首选）

原理：用数组保存当前路径，往下走就加入节点，回溯的时候删掉；遇到叶子比较长度，记录最长路径。

#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; int maxDep = 0; int ansPath[100]; int curPath[100]; void dfs(TreeNode *root, int depth, int idx) { if(root == NULL) return; curPath[idx] = root->val; // 叶子节点 if(root->left == NULL && root->right == NULL) { if(depth > maxDep) { maxDep = depth; // 复制到答案路径 for(int i = 0; i <= idx; i++) { ansPath[i] = curPath[i]; } } return; } dfs(root->left, depth+1, idx+1); dfs(root->right, depth+1, idx+1); } TreeNode* createNode(int v) { TreeNode *n = malloc(sizeof(TreeNode)); n->val = v; n->left = n->right = NULL; return n; } int main() { TreeNode *root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); dfs(root,1,0); printf("max depth=%d\n",maxDep); printf("path:"); for(int i=0;i<maxDep;i++){ printf("%d ",ansPath[i]); } return 0; }