一文彻底搞清楚遍历二叉树和OJ算法题的暴力美学全面解析

承渊政道

发布于 2025-12-18 17:26:07

1580

🔥承渊政道：个人主页 ❄️个人专栏: 《C语言基础语法知识》《数据结构与算法初阶》 ✨逆境不吐心中苦,顺境不忘来时路! 🎬 博主简介:

前言:前面小编已经介绍完了关于二叉树中堆的介绍,但二叉树的相关内容并没有结束,本篇继续介绍二叉树的相关内容,并进入二叉树相关算法题的暴力美学当中!废话不多说,下面跟着小编的节奏🎵一起学习吧！

1.实现链式结构⼆叉树

⽤链表来表示⼀棵⼆叉树,即⽤链来指示元素的逻辑关系.通常的⽅法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址,其结构如下: typedef int BTDataType; // ⼆叉链 typedef struct BinaryTreeNode { struct BinTreeNode* left; // 指向当前结点左孩⼦ struct BinTreeNode* right; // 指向当前结点右孩⼦ BTDataType val; // 当前结点值域 }BTNode; ⼆叉树的创建⽅式⽐较复杂,为了更好的步⼊到⼆叉树内容中,我们先⼿动创建⼀棵链式⼆叉树

BTNode* BuyBTNode(int val)
 {
 BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
 if (newnode == NULL)
 {
 perror("malloc fail");
 return NULL;
 }
 newnode->val = val;
 newnode->left = NULL;
 newnode->right = NULL;
 return newnode;
 }
 BTNode* CreateTree()
 {
 BTNode* n1 = BuyBTNode(1);
 BTNode* n2 = BuyBTNode(2);
 BTNode* n3 = BuyBTNode(3);
 BTNode* n4 = BuyBTNode(4);
 BTNode* n5 = BuyBTNode(5);
 BTNode* n6 = BuyBTNode(6);
 BTNode* n7 = BuyBTNode(7);
 n1->left = n2;
 n1->right = n4;
 n2->left = n3;
 n4->left = n5;
 n4->right = n6;
 n5->left = n7;
 return n1;
 }

回顾⼆叉树的概念,⼆叉树分为空树和⾮空⼆叉树,⾮空⼆叉树由根结点、根结点的左⼦树、根结点的右⼦树组成的.根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的,因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的.

1.1前中后序遍历

⼆叉树的操作离不开树的遍历,我们先来看看⼆叉树的遍历有哪些⽅式?

前序遍历:ABD(NULL)(NULL)(NULL)CE(NULL)(NULL)F(NULL)(NULL) 中序遍历:(NULL)D(NULL)B(NULL)A(NULL)E(NULL)C(NULL)F(NULL) 后序遍历:(NULL)(NULL)D(NULL)B(NULL)(NULL)E(NULL)(NULL)FCA NULL可以省略不写,只是小编让你们看的更直观一点!

1.1.1遍历规则

按照规则,⼆叉树的遍历有:前序/中序/后序的递归结构遍历: 1️⃣前序遍历(亦称先序遍历):访问根结点的操作发⽣在遍历其左右⼦树之前. 访问顺序为:根结点、左⼦树、右⼦树.可以简计为根左右 2️⃣中序遍历:访问根结点的操作发⽣在遍历其左右⼦树之中(间). 访问顺序为:左⼦树、根结点、右⼦树.可以简计为左根右 3️⃣后序遍历:访问根结点的操作发⽣在遍历其左右⼦树之后访问顺序为:左⼦树、右⼦树、根结点.可以简计为左右根

1.1.2前中后序遍历代码实现

//前序遍历——根左右
void preOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	preOrder(root->left);
	preOrder(root->right);
}

//中序遍历--左根右
void inOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	inOrder(root->left);
	printf("%c ", root->data);
	inOrder(root->right);
}

//后序遍历--左右根
void postOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	postOrder(root->left);
	postOrder(root->right);
	printf("%c ", root->data);
}

图解遍历:以前序遍历为例

函数递归栈帧图：

前序遍历结果:123456 中序遍历结果:321546 后序遍历结果:315641

1.2计算二叉树结点个数、⾼度、查找某个结点的值以及销毁二叉树

//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left)
		+ BinaryTreeSize(root->right);
}//结点个数=根结点+左子树结点个数+右子树结点个数

// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left)
		+ BinaryTreeLeafSize(root->right);
}//叶子结点个数=左子树叶子结点个数+右子树结点个数

// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left)
		+ BinaryTreeLeafSize(root->right);
}//第k层结点个数=左子树第k层结点个数+右子树中第k层结点个数

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
    return 1 + (leftDep > rightDep ? leftDep : rightDep);
}//二叉树高度=根结点+max(左子树，右子树)

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

// ⼆叉树销毁--左右根
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

1.3层序遍历

除了先序遍历、中序遍历、后序遍历外,还可以对⼆叉树进⾏层序遍历.设⼆叉树的根结点所在层数为1,层序遍历就是从所在⼆叉树的根结点出发,⾸先访问第⼀层的树根结点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,⾃上⽽下,⾃左⾄右逐层访问树的结点的过程就是层序遍历实现层序遍历需要额外借助数据结构:队列.

涉及关于队列的代码小编在这里就不展示了,可以看看前面关于队列介绍.

// 层序遍历
 void LevelOrder(BTNode* root)
 {
 Queue q;
 QueueInit(&q);
 QueuePush(&q, root);
 while (!QueueEmpty(&q))
 {
 BTNode* top = QueueFront(&q);
 printf("%c ", top->data);
 QueuePop(&q);
 if (top->_left)
 QueuePush(&q, top->_left);
 if (top->_right)
 QueuePush(&q, top->_right);
 }
 QueueDesTroy(&q);
 }

1.4判断是否为完全⼆叉树

我们先回顾完全二叉树的特点:1️⃣最后一层结点的个数不一定达到最大2️⃣结点从左到右依次排列

我们得出:若在第二个循环中,从非空队列中取到了非空的队头结点,那么该二叉树一定不是完全二叉树,否则一定是完全二叉树.

// 判断⼆叉树是否是完全⼆叉树
 bool BinaryTreeComplete(BTNode* root)
 {
 Queue q;
 QueueInit(&q);
 QueuePush(&q, root);
 while (!QueueEmpty(&q))
 {
 //取队头结点,出队头
 BTNode* top = QueueFront(&q);
 QueuePop(&q);
 if (top == NULL)
 {
 break;
 }
 QueuePush(&q, top->_left);
 QueuePush(&q, top->_right);
 }//队列不一定为空
 while (!QueueEmpty(&q))
 {
 BTNode* top = QueueFront(&q);
 QueuePop(&q);
 if (top != NULL)
 {
 QueueDesTroy(&q);
 return false;
 }
 }
 QueueDesTroy(&q);
 return true;
 }

2.二叉树算法题

2.1单值二叉树

bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    if(root->left && root->val != root->left->val)
    {
        return false;
    }
    if(root->right && root->val != root->right->val)
    {
        return false;
    }
    //根节点和左右孩子结点的值都是相同
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}//代码解析:函数isUnivalTree接收二叉树的根节点指针root,返回一个布尔值：
//true:这棵树是单值树(所有节点的值都相同)
//false:这棵树不是单值树(存在至少两个不同值的节点)
//如果传入的根节点是NULL(表示空树,或递归到了叶子节点的子节点),返回true
//如果左子节点存在(root->left不为NULL),且根节点的值≠左子节点的值,直接返回false
//逻辑与左子节点完全一致:判断右子节点存在且根节点的值≠右子节点的值,若满足则返回false
//递归调用isUnivalTree(root->left):判断左子树是否为单值树
//递归调用isUnivalTree(root->right):判断右子树是否为单值树

2.2相同的树

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //都为空
    if(p == NULL && q == NULL)
    {
        return true;
    }
    //其中一个非空
    if( p == NULL || q == NULL)
    {
        return false;
    }
    //都不为空---p q val
    if(p->val != q->val)
    {
        return false;
    }
    //结构相同 + 值相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}//代码解析:函数isSameTree接收两棵二叉树的根节点指针p和q,返回一个布尔值：
//true:两棵树是相同树(结构完全一样,对应节点值全部相同)
//false:两棵树不同(要么结构不同,要么对应节点值不同)
//如果两棵树的当前节点都为NULL(表示空树,或递归到了叶子节点的子节点),返回true
//如果其中一个节点是NULL,另一个不是NULL(用 || 短路判断),直接返回false
//经过前两步判断后,p和q都不为NULL(结构上当前节点一致),此时检查两者的值是否相同——不同则返回false
//递归调用isSameTree(p->left, q->left):判断两棵树的左子树是否相同
//递归调用isSameTree(p->right, q->right):判断两棵树的右子树是否相同

2.3对称二叉树

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL)
    {
        return true;
    }
    if(p == NULL || q == NULL)
    {
        return false;
    }
    //p和q都不为空
    if(p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->right) && isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) {
    return isSameTree(root->left,root->right);
}//代码解析:isSymmetric函数判断二叉树是否对称,核心逻辑是:对称树的左子树和右子树必须是镜像关系,因此通过改造后的isSameTree函数,专门校验两个子树是否镜像,从而实现对称判断
//对称树的本质是左子树 ≌ 右子树的镜像,因此把左子树当作基准树p,右子树当作待校验的镜像树q,通过改造后的 isSameTree校验两者是否镜像即可
//边界补充:若root为NULL(空树),root->left和root->right也为NULL,调用isSameTree(NULL, NULL) 会返回true,符合空树是对称树的定义
//两个节点都为空,返回true
//一个节点为空、另一个不为空,返回false
//经过前两步,p和q都非空(对应注释p和q都不为空)若值不同,返回false
//与相同树校验的核心差异:之前判断相同树是p左对q左、p右对q右(同方向对比);现在校验镜像树是p左对q右、p右对q左(交叉方向对比)——这是镜像关系的本质(A的左边对应B的右边,A的右边对应B的左边)
//只有p的左子树与q的右子树是镜像且p的右子树与q的左子树是镜像,才能说明p和q对应的两棵树是镜像

2.4另一棵树的子树

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //都为空
    if(p == NULL && q == NULL)
    {
        return true;
    }
    //其中一个非空
    if( p == NULL || q == NULL)
    {
        return false;
    }
    //都不为空---p q val
    if(p->val != q->val)
    {
        return false;
    }
    //结构相同 + 值相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root == NULL)
    {
        return false;
    }
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}//代码解析:函数isSameTree:负责判断两棵树是否完全相同(结构一致+对应节点值相同),是子树判断的基础
//函数isSubtree:负责遍历root的所有节点,以每个节点为根,调用isSameTree校验是否与subRoot完全相同,只要找到一个匹配的子树就返回true
//先校验结构一致性(都空/都非空),再校验值一致性,最后递归校验子树一致性(同方向对比:p左对q左、p右对q 右)
//如果root已经遍历到空节点(说明前面所有节点都没匹配到subRoot),返回false
//检查以当前root为根的树是否和subRoot完全相同(结构+值)
//当前节点不匹配时,递归遍历root的左子树和右子树,继续找匹配的节点

2.5二叉树的前序遍历

typedef struct TreeNode TreeNode;
//结点总数 = 1 + 左子树结点个数 + 右子树结点个数
int TreeSize(TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}
void preOrder(TreeNode* root,int* arr,int* pi)
{
    if(root == NULL)
    {
        return;
    }
    //保存根节点的值到数组中
    arr[(*pi)++] = root->val;
    preOrder(root->left,arr,pi);
    preOrder(root->right,arr,pi);
}
//数组大小——求二叉树所有节点的个数
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    //求二叉树结点的个数
    *returnSize = TreeSize(root);
    //数组要申请*returnSize个int空间
    int* arr = (int*)malloc(sizeof(int)*(*returnSize));
    //前序遍历
    int i = 0;
    preOrder(root,arr,&i);
    return arr;
}//代码解析:调用TreeSize函数计算二叉树的总节点数,将结果赋值给returnSize指向的变量；
//关键:returnSize是输出参数(C语言无法直接返回多个值,通过指针修改外部变量),目的是告诉函数调用者"返回的数组有多少个元素"
//根据节点总数*returnSize,动态申请一块连续的内存(数组),用于存储遍历结果;为什么用动态内存?因为二叉树的节点数是不确定的,无法提前定义固定大小的数组,必须先计算大小再申请对应空间
//定义计数器i(初始为0,标记数组的当前存储位置),调用preOrder函数执行递归前序遍历,将节点值存入数组;关键:i传递的是地址(&i),而非普通值——因为递归调用会多层嵌套,普通变量会在每层递归中重新初始化,无法保持计数的连续性;传递地址可以让所有递归层级共享同一个计数器,确保值能依次存入数组的正确位置
//如果当前节点是NULL(空节点,或递归到叶子节点的子节点),返回0
//当前节点的总节点数=1(当前节点本身)+左子树的节点数(递归调用TreeSize(root->left))+右子树的节点数（递归调用TreeSize(root->right)）
//如果当前节点是NULL,直接返回(无需存储值)
//先通过*pi拿到当前数组的存储下标(pi是指针,*pi是计数器的当前值),将当前节点的val存入数组对应位置;然后pi自增(++),为下一个节点值预留位置
//处理完当前根节点后,递归遍历左子树,重复存根→左→右的流程
//左子树遍历完成后,递归遍历右子树

2.6二叉树的中序遍历

typedef struct TreeNode TreeNode;
// 结点总数 = 1 + 左子树结点个数 + 右子树结点个数
int TreeSize(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}
void inOrder(TreeNode* root, int* arr, int* pi) {
    if (root == NULL) {
        return;
    }
    // 中序遍历核心顺序：先递归左子树
    inOrder(root->left, arr, pi);
    // 再保存根节点的值到数组中（中序：左→根→右）
    arr[(*pi)++] = root->val;
    // 最后递归右子树
    inOrder(root->right, arr, pi);
}
// 数组大小——求二叉树所有节点的个数
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    // 求二叉树结点的个数（确定数组大小）
    *returnSize = TreeSize(root);
    // 数组要申请*returnSize个int空间
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    // 中序遍历
    int i = 0;
    inOrder(root, arr, &i);
    return arr;
}//代码解析:root是当前遍历节点,arr是存储结果的数组,pi是数组索引计数器的指针(重点!)
//为什么pi是指针?递归会创建多层函数栈帧,若pi是普通变量,每层递归的pi会独立初始化(计数重置);传递指针可让所有递归层级共享同一个计数器,确保节点值依次存入数组的正确位置(比如i=0存第一个值,i=1存第二个,不会乱序）
//先钻透左子树:递归调用inOrder(root->left),直到左子节点为NULL(左子树处理完毕);
//再存当前根节点:用(*pi)取当前计数器值(数组下标),存入节点值后,pi自增(++),为下一个值预留位置;最后处理右子树:递归调用inOrder(root->right),重复左→根→右流程
//计算节点数→*returnSize=TreeSize(root):returnSize是输出参数(C语言无法直接返回多个值,通过指针修改外部变量),目的是让调用者知道返回的数组有多少个元素
//动态申请数组内存→int*arr=(int*)malloc(...):按节点总数*returnSize申请内存,避免固定数组 “不够用” 或 “浪费空间” 的问题
//触发中序遍历→inOrder(root, arr, &i):初始化计数器i=0(数组起始下标),传递i的地址(&i)给 inOrder,确保递归中计数连续；

2.7二叉树的后序遍历

typedef struct TreeNode TreeNode;
// 结点总数 = 1 + 左子树结点个数 + 右子树结点个数
int TreeSize(TreeNode* root) {
    if (root == NULL) {
        return 0; // 空节点无节点数，递归终止
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}
void postOrder(TreeNode* root, int* arr, int* pi) {
    if (root == NULL) {
        return; // 空节点直接返回，递归终止
    }
    // 后序遍历核心顺序：1. 先递归左子树
    postOrder(root->left, arr, pi);
    // 2. 再递归右子树
    postOrder(root->right, arr, pi);
    // 3. 最后保存根节点的值（后序：左→右→根）
    arr[(*pi)++] = root->val;
}
// 数组大小——求二叉树所有节点的个数
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    // 求二叉树结点的个数（确定数组大小）
    *returnSize = TreeSize(root);
    // 数组要申请*returnSize个int空间
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    // 后序遍历
    int i = 0;
    postOrder(root, arr, &i);
    return arr;
}//代码解析:调用TreeSize(root)→递归统计二叉树总节点数n→returnSize= n；
//按n申请大小为n*sizeof(int)的动态数组arr;初始化计数器i=0,调用postOrder(root, arr, &i);
//postOrder按左→右→根递归遍历:先递归左子树,所有左子节点处理完毕后,递归右子树;
//左、右子树均处理完,再将当前根节点值存入数组,计数器i自增;
//所有节点处理完毕,postorderTraversal返回arr首地址,returnSize已被修改为数组长度;
//调用者通过res访问遍历结果,通过returnSize知道数组长度,使用后释放res

2.8二叉树的遍历

//二叉树链式结构
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode{
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;
TreeNode* buyNode(char ch)
{
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    if(node == NULL)
    {
        exit(1);
    }
    node->data = ch;
    node->left = node->right = NULL;
    return node;
}
TreeNode* createTree(char* arr,int* pi)
{
    if(arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    TreeNode* root = buyNode(arr[*pi]);
    (*pi)++;
    root->left = createTree(arr, pi);
    root->right = createTree(arr,pi);
    return root;
}
//中序--左根右
void inOrder(TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }
    inOrder(root->left);
    printf("%c ",root->data);
    inOrder(root->right);
}
int main()
{
    //读取输入的前序遍历字符串
    char arr[100];
    scanf("%s",arr);
    //根据前序遍历字符串创建二叉树
    int i = 0;
    TreeNode* root = createTree(arr, &i);
    //二叉树的中序遍历
    inOrder(root);
    return 0;
}//代码解析:arr是输入的前序字符串,pi是字符串索引的指针.空节点处理:若当前字符是#,说明当前位置是空节点,索引自增(跳过#)并返回NULL.根节点创建:若不是#,调用buyNode创建当前根节点,值为当前字符arr[*pi]
//索引自增:(*pi)++——必须通过指针操作(而非普通变量),因为递归会多层嵌套,普通变量会在每层栈帧中重置,指针能让所有递归层级共享同一个索引,确保字符串按顺序依次处理
//递归构建子树:先递归创建左子树(前序的左）,再递归创建右子树(前序的右),最终返回当前根节点,完成与父节点的连接
//按左→根→右的中序规则遍历二叉树,打印每个节点的data
//终止条件:root==NULL(空节点无需处理,直接返回)
//核心流程:输入→构建树→遍历输出