当前位置： 首页 > news >正文

异世界历险之数据结构世界（二叉树-leetcode）

news 2025/7/20 7:34:22

前言

在这里插入图片描述

实战演练

  1. 单值二叉树。OJ
  2. 检查两颗树是否相同。OJ
  3. 对称二叉树OJ

Question

Question 1

在这里插入图片描述

Method

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isUnivalTree(struct TreeNode* root) {if(root == NULL) return true;if(root->left && root->left->val != root->val)return false;if(root->right && root->right->val != root->val)return false;
return isUnivalTree(root->left) && isUnivalTree(root->right);
}

Topic analysis

根节点与左右孩子比较
若当前节点不满足单值条件直接返回 false
否则递归检查子树，所有子树都满足才返回 true

递归展开：

  1. 最外层调用 isUnivalTree(root)：
    检查根节点：
    root != NULL
    root->val == 1
    继续检查左右子树。
    递归检查左子树：isUnivalTree(root->left)
    递归检查右子树：isUnivalTree(root->right)
  1. 递归调用 isUnivalTree(root->left)：
    检查左子树的根节点：
    root->val == 1，root->left->val == 1，root->right->val == 1
    继续递归检查左右子树。
    递归检查左子树的左子树：isUnivalTree(root->left->left)
    递归检查左子树的右子树：isUnivalTree(root->left->right)
  1. 递归调用 isUnivalTree(root->left->left) 和 isUnivalTree(root->left->right)：
    这两个节点都是叶子节点，值都为 1，都返回 true。
    因此，isUnivalTree(root->left) 返回 true。
  1. 递归调用 isUnivalTree(root->right)：
    检查右子树的根节点：
    root->val == 1，右子树也满足条件，递归调用 isUnivalTree(root->right->left) 和 isUnivalTree(root->right->right)。
    因为 root->right 是叶子节点且值为 1，返回 true。
  1. 最终返回：
    isUnivalTree(root) 会返回 isUnivalTree(root->left) && isUnivalTree(root->right)。
    所以，最终结果是 true && true，返回 true。

Question2

在这里插入图片描述

Method

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p==NULL && q==NULL) return true;if(p==NULL || q==NULL) return false;if(p->val != q->val) return false;return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

Topic analysis

比较空树的情况：
if (p == NULL && q == NULL) return true;
如果两棵树都为空，那么它们自然是相同的，返回 true。
其中一棵树为空：
if (p == NULL || q == NULL) return false;
如果其中一棵树为空，另一棵树不为空，那么它们不可能相同，返回 false。
当前节点的值不同：
if (p->val != q->val) return false;
如果当前节点的值不同，那么两棵树肯定不同，返回 false。
递归检查左右子树：
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
如果当前节点的值相同，我们就继续递归地检查左子树和右子树是否相同。
只有当左右子树都相同，整个树才能被认为是相同的，所以使用 && 运算符连接两个递归调用。

递归展开类似上道题目。
调用 isSameTree(root1, root2)：
比较根节点：1 == 1，继续检查左右子树。
递归调用 isSameTree(root1->left, root2->left)：

比较左子树根节点：2 == 2，继续检查左右子树。
递归调用 isSameTree(root1->left->right, root2->left->right)：
root1->left->right == NULL，root2->left->right == NULL，返回 true。
递归调用 isSameTree(root1->right, root2->right)：

比较右子树根节点：3 == 3，继续检查左右子树。
递归调用 isSameTree(root1->right->left, root2->right->left)：
root1->right->left == NULL，root2->right->left == NULL，返回 true。
递归调用 isSameTree(root1->right->right, root2->right->right)：
root1->right->right == NULL，root2->right->right == NULL，返回 true。
最终，因为所有的递归都返回了 true，所以 isSameTree(root1, root2) 返回 true。

Question3

在这里插入图片描述

Method

bool isMirror(struct TreeNode* t1,struct TreeNode* t2)
{if(t1==NULL && t2==NULL) return true;if(t1==NULL || t2==NULL) return false;if(t1->val != t2->val) return false;return isMirror(t1->left,t2->right) && isMirror(t1->right,t2->left);
}bool isSymmetric(struct TreeNode* root) {if(root == NULL) return true;return isMirror(root->left,root->right);
}

Topic analysis

isMirror函数：
逻辑分析：
空树判断：如果两棵树都为空，说明它们是对称的，返回 true；如果其中一个为空，另一个不为空，说明它们不对称，返回 false。
节点值比较：如果两个节点的值不同，它们不可能对称，返回 false。
递归检查：
递归地检查左子树和右子树是否镜像对称，具体来说，t1->left 应该与 t2->right 对称，t1->right 应该与 t2->left 对称。

isSymmertric函数：
逻辑分析：
空树判断：如果树的根节点是 NULL，树自然是对称的，返回 true。
调用 isMirror：如果根节点不为空，我们就调用 isMirror 来判断左子树和右子树是否镜像对称。

实战演练

4.二叉树前序遍历
5.另一颗树的子树。

Question

Question4

在这里插入图片描述

Method

int TreeSize(struct TreeNode* root)
{return root == NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}void Preorder(struct TreeNode* root,int*arr,int* i)
{   if(root == NULL) return ;arr[(*i)++] = root->val;Preorder(root->left,arr,i);Preorder(root->right,arr,i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* arr = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;Preorder(root,arr,&i);return arr;
}

Topic analysis

TreeSize 函数：
逻辑分析：
空树判断：如果当前节点为空（即树为空），则节点数为 0。
递归计算：如果当前节点不为空，递归地计算左子树和右子树的节点数，并加上当前节点的 1，得到整棵树的节点数。

PreOrder函数：
逻辑分析：
空树判断：如果当前节点为空，直接返回，不做任何操作。
访问根节点：将当前节点的值 root->val 存入数组 arr，并递增 i，表示数组的下一个位置。
递归遍历：首先递归遍历左子树，然后递归遍历右子树。

preorderTraversal函数:
逻辑分析：
计算树的节点数：首先调用 TreeSize(root)，得到树 root 的节点总数，并存储在 *returnSize 中。
分配内存：根据树的节点数，分配一个数组 arr，用于存储前序遍历的结果。
执行前序遍历：调用 Preorder(root, arr, &i) 来进行前序遍历，arr 用于存储结果，i 用来追踪当前存储的位置。
返回结果：最后返回存储前序遍历结果的数组 arr。

Error Reminder

在 Preorder 函数中，i 用来记录当前遍历到的节点位置（数组的下标）。我们通过递归遍历二叉树的每个节点，并将它们的值依次存入数组中。

为什么要传递指针而不是值？
递归函数的每次调用都会有一个独立的作用域。如果我们将 i 作为 值 传递，那么每次递归调用时 i 会被拷贝到一个新的变量，这意味着递归调用中的每个 i 都是独立的，它们不会相互影响。
但是，我们希望在递归过程中能够共享同一个 i 值，让它在每次递归时都能够“记住”之前的值，以便正确地更新数组的下标。这就需要传递 i 的 指针，从而确保递归中的每个调用都操作的是同一个 i，而不是各自的副本。

具体分析：
传递值（错误方式）：
如果我们传递 i 的值，每次递归时，i 的副本会被创建，递归函数中的 i 会独立于父调用中的 i。这样在递归过程中，i 就不能准确地追踪遍历到的位置，导致数组下标出错。

void Preorder(struct TreeNode* root, int* arr, int i) {  // 错误，i 是值传递if (root == NULL) return;arr[i++] = root->val;Preorder(root->left, arr, i);  // 传递副本，不影响原来的 iPreorder(root->right, arr, i); // 同上
}

在这个例子中，i 的值会被传递给每个递归调用的副本，导致递归过程中的 i 在每一层都没有被正确更新，从而使得最终的数组存储位置错误。

传递指针（正确方式）：
当我们传递 i 的指针（int* i）时，所有递归调用都操作同一个 i。每次递归时，对 i 的更新都会影响到其他递归调用，确保下标位置不断递增。

void Preorder(struct TreeNode* root, int* arr, int* i) {  // 正确，i 是指针传递if (root == NULL) return;arr[(*i)++] = root->val;   // 操作同一个 iPreorder(root->left, arr, i);  // 递归，i 继续共享Preorder(root->right, arr, i); // 同上
}

这样，在每一次递归调用中，i 的更新都会影响到父函数的 i，确保递归遍历过程中数组的位置被正确更新。

Question5

在这里插入图片描述

Method

bool isSameTree(struct TreeNode* t1,struct TreeNode* t2)
{if(t1==NULL && t2==NULL) return true;if(t1==NULL || t2==NULL) return false;if(t1->val != t2->val) return false;return isSameTree(t1->left,t2->left) && isSameTree(t1->right,t2->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);
}

Topic analysis

第一个函数不作解释。
逻辑分析：
空树判断：如果 root 为空，说明无法找到子树 subRoot，返回 false。
完全匹配：如果 root 和 subRoot 完全相同，说明 subRoot 是 root 的子树，返回 true。此时使用 isSameTree 来比较两个树是否完全相同。
递归搜索：如果当前节点不匹配，递归检查左子树和右子树，看看 subRoot 是否出现在其中一个子树中。

递归展开：
调用 isSubtree(root, subRoot)：
检查 root 和 subRoot 是否完全相同。使用 isSameTree(root, subRoot)。
root->val == 3 和 subRoot->val == 4，值不同，返回 false。
继续递归检查 root 的左右子树。
递归调用 isSubtree(root->left, subRoot)：
root->left 的值是 4，与 subRoot 完全相同。此时，调用 isSameTree(root->left, subRoot)，返回 true。
因此，isSubtree(root, subRoot) 返回 true。

总结：这是补充的二叉树部分内容。

http://www.lryc.cn/news/593195.html

相关文章：

  • 国产电科金仓数据库：融合进化，智领未来
  • 【Unity3D实例-功能-移动】角色移动-通过WSAD（Rigidbody方式）
  • 架构探索笔记【1】
  • JavaScript空值安全深度指南
  • windows内核研究（驱动开发之内核编程）
  • Java无服务架构新范式：Spring Native与AWS Lambda冷启动深度优化
  • 【小沐学GIS】基于Rust绘制三维数字地球Earth（Rust、OpenGL、GIS）
  • C++STL系列之概述
  • OpenCV 官翻5 - 机器学习
  • 【web安全】万能密码
  • 物联网系统中的可视化大屏定义
  • UGUI 性能优化系列：第三篇——渲染与像素填充率优化
  • 小明记账簿焕新记：从单色到多彩的主题进化之路
  • 【Android】ListView与RecyclerView的基础使用
  • 安全隔离新选择：SiLM5768L系列 - 集成互锁功能的高速六通道数字隔离器
  • 从随机数值到特征检测器的学习与更新
  • 【Linux驱动-快速回顾】简单了解一下PinCtrl子系统：设备树如何被接解析与匹配
  • 大模型 Function Call 的实现步骤及示例详解
  • SpringBoot 3.0 挥别 spring.factories，拥抱云原生新纪元
  • Java机考题：815. 公交路线 图论BFS
  • 猎板：在 5G 与 AI 时代，印制线路板如何满足高性能需求
  • SQL Server和PostgreSQL填充因子
  • 数据结构与算法之美：拓扑排序
  • 小谈相机的学习过程
  • ROS2 通过相机确定物品坐标位置
  • MySQL数据丢失救援办法
  • 异步解决一切问题 |消息队列 |减少嵌套 |hadoop |rabbitmq |postsql
  • 智能体之变：深度解析OpenAI ChatGPT Agent如何重塑人机协作的未来
  • 【Qt开发】Qt的背景介绍（三）-＞ 认识Qt Creator
  • 论文略读：Are Large Language Models In-Context Graph Learners?