网站电子签名怎么做,西安优化网站,wordpress轮播图源码,四大商业网站个人主页#xff1a;C忠实粉丝 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 C忠实粉丝 原创 二叉树经典OJ练习 收录于专栏【数据结构初阶】 本专栏旨在分享学习数据结构学习的一点学习笔记#xff0c;欢迎大家在评论区交流讨论#x1f48c; 目录 前置说… 个人主页C忠实粉丝 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 C忠实粉丝 原创 二叉树经典OJ练习 收录于专栏【数据结构初阶】 本专栏旨在分享学习数据结构学习的一点学习笔记欢迎大家在评论区交流讨论 目录 前置说明
1. 单值二叉树
2. 相同的树
3. 对称二叉树
4. 二叉树的前序遍历
5. 二叉树中序遍历
6. 二叉树的后序遍历
7. 另一颗树的子树 前置说明
这里大家需要有二叉树的一些基础,还不是很了解的宝子们可以点击下方链接进行查看
---数据结构之二叉树的超详细讲解(3)--(二叉树的遍历和操作)-CSDN博客
1. 单值二叉树
Oj链接--965. 单值二叉树 - 力扣LeetCode
题目描述:
如果二叉树每个节点都具有相同的值那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时才返回 true否则返回 false。 示例 1 输入[1,1,1,1,1,null,1]
输出true示例 2 输入[2,2,2,5,2]
输出false提示
给定树的节点数范围是 [1, 100]。每个节点的值都是整数范围为 [0, 99] 。
分析: 题目中给定树的节点数范围是 [1, 100],这里我们就不需要额外判断空节点的情况,我们只需要对二叉树进行遍历一遍,如果遇到空节点返回true,如果root左节点或右节点val不等于root-val,返回false,将最后的结果上传,即可得到最终的结果. 代码展示:
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);
} 核心逻辑 空树检查 if(root NULL) return true; 这里首先检查根节点是否为空。如果根节点为空则该树被认为是单值二叉树返回 true。 左子节点值检查 if(root-left root-left-val ! root-val) return false; 接下来检查左子节点。如果左子节点存在且其值与根节点的值不相同则该树不是单值二叉树返回 false。 右子节点值检查 if(root-right root-right-val ! root-val) return false; 同样地检查右子节点。如果右子节点存在且其值与根节点的值不相同则该树不是单值二叉树返回 false。 递归检查子树 return isUnivalTree(root-left) isUnivalTree(root-right); 如果当前节点及其直接子节点都满足条件则递归检查左子树和右子树。只有在左右子树都是单值二叉树的情况下当前树才是单值二叉树。 总结 该函数通过递归检查每个节点及其子节点的值是否与根节点的值相同来判断整个二叉树是否是单值二叉树。如果某个节点的值与其父节点不同立即返回 false。否则继续递归检查其子树最终返回整个树的结果。 2. 相同的树
OJ链接--100. 相同的树 - 力扣LeetCode
题目描述:
给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 示例 1 输入p [1,2,3], q [1,2,3]
输出true示例 2 输入p [1,2], q [1,null,2]
输出false示例 3 输入p [1,2,1], q [1,1,2]
输出false提示
两棵树上的节点数目都在范围 [0, 100] 内-104 Node.val 104
分析: 两棵树上的节点数目都在范围 [0, 100] 内,说明这里需要进行空树的判断,我们需要先进行判断,当两棵树节点都为空时,满足条件,返回true.当两个节点只有一个为空时,不满足条件,返回false.当两个节点都不为空时,比较两个节点的val,不相等返回false.然后递归遍历两棵树. 代码展示:
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);
} 首先检查 p 和 q 是否同时为 NULL如果是说明两棵树都为空返回 true。然后检查 p 和 q 是否其中一个为 NULL另一个不是。如果是说明两棵树中的节点个数不同返回 false。接着检查 p 和 q 的当前节点值是否相同如果不同返回 false。最后通过递归调用 isSameTree 函数比较两棵树的左子树和右子树是否相同如果均相同则返回 true否则返回 false。 这段代码非常简洁而且有效地比较了两棵树是否相同。它利用了递归的特性逐层比较树的节点值以及对应的子树从而判断两棵树是否相同。 3. 对称二叉树
OJ链接--101. 对称二叉树 - 力扣LeetCode
题目描述:
给你一个二叉树的根节点 root 检查它是否轴对称。 示例 1 输入root [1,2,2,3,4,4,3]
输出true示例 2 输入root [1,2,2,null,3,null,3]
输出false提示
树中节点数目在范围 [1, 1000] 内-100 Node.val 100
代码展示:
bool check(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 check(p-left, q-right) check(p-right, q-left);elsereturn false;
}bool isSymmetric(struct TreeNode* root) {return check(root, root);
}
分析: check 函数 首先检查 p 和 q 是否同时为 NULL如果是说明两个节点都为空返回 true。然后检查 p 和 q 是否其中一个为 NULL另一个不是。如果是说明两个节点中的一个为空另一个不为空返回 false。接着检查 p 和 q 的值是否相等如果相等则递归地比较 p 的左子树和 q 的右子树以及 p 的右子树和 q 的左子树是否对称。如果均对称则返回 true否则返回 false。 isSymmetric 函数 调用 check 函数并传入根节点的左右子树作为参数进行比较。 这段代码利用递归的方式判断了一棵二叉树是否对称。它通过比较树的左右子树是否镜像对称来判断整棵树是否对称。整体上这段代码实现了一个简洁而有效的对称性判断算法。 函数递归展开图: 4. 二叉树的前序遍历
OJ链接--144. 二叉树的前序遍历 - 力扣LeetCode
题目描述:
给你二叉树的根节点 root 返回它节点值的 前序 遍历。 示例 1 输入root [1,null,2,3]
输出[1,2,3]示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]示例 4 输入root [1,2]
输出[1,2]示例 5 输入root [1,null,2]
输出[1,2]提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100
分析: 注意这道题目的要求: /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* preorderTraversal(struct TreeNode* root, int* returnSize) {} 这里我们需要返回的是前序遍历好的数组,而且需要我们自己malloc创建.函数的参数一个是根节点一个是节点个数,要我们实现的是一个输出型函数. 代码展示:
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}void preOrder(struct TreeNode* root, int* a, int* pi)
{if(root NULL)return;a[(*pi)] root-val;preOrder(root-left, a, pi);preOrder(root-right, a, pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize TreeSize(root);int* a (int*)malloc(sizeof(int)*(*returnSize));int i 0;preOrder(root, a, i);return a;
} 这段代码是关于二叉树前序遍历的实现其中包括了计算二叉树节点总数和返回前序遍历结果的功能。让我们对这段代码进行详细分析 int TreeSize(struct TreeNode* root) { return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1; } 这部分代码是计算二叉树节点总数的函数 TreeSize使用了递归的方式来统计节点数量。在每个节点上它会递归地调用自身来计算左子树和右子树的节点数并加上当前节点。 void preOrder(struct TreeNode* root, int* a, int* pi) { if(root NULL) return; a[(*pi)] root-val; preOrder(root-left, a, pi); preOrder(root-right, a, pi); } 这部分代码是实现前序遍历的函数 preOrder它将遍历得到的节点值存储在数组 a 中使用指针 pi 来跟踪数组的索引位置。 int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize TreeSize(root); int* a (int*)malloc(sizeof(int)*(*returnSize)); int i 0; preOrder(root, a, i); return a; } 最后preorderTraversal 函数整合了前两部分的功能。它先计算二叉树的节点总数然后动态分配一个数组 a 来存储前序遍历的结果并调用 preOrder 函数来填充数组。最终将数组返回。 总结 这段代码实现了计算二叉树节点总数并返回其前序遍历结果的功能。通过递归的方式遍历二叉树将节点值按前序遍历顺序存储在数组中并返回该数组。这样的实现使得我们能够方便地获取二叉树的前序遍历结果并且能够有效地处理动态分配内存以存储结果。 5. 二叉树中序遍历
OJ链接--94. 二叉树的中序遍历 - 力扣LeetCode
题目描述:
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 示例 1 输入root [1,null,2,3]
输出[1,3,2]示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100 后面的中序和后序跟前序相差不大,这里就不过多解释. 代码展示:
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}void inOrder(struct TreeNode* root, int* a, int* pi)
{if(root NULL){return;}inOrder(root-left,a,pi);a[(*pi)] root-val;inOrder(root-right,a,pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize TreeSize(root);int* a (int*)malloc(sizeof(int)*(*returnSize));int i 0;inOrder(root,a,i);return a;
}
6. 二叉树的后序遍历
OJ链接--145. 二叉树的后序遍历 - 力扣LeetCode
题目描述:
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 示例 1 输入root [1,null,2,3]
输出[3,2,1]示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]提示
树中节点的数目在范围 [0, 100] 内-100 Node.val 100
代码展示:
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}void postOrder(struct TreeNode* root, int* a, int* pi)
{if(root NULL)return;postOrder(root-left, a, pi);postOrder(root-right, a, pi);a[(*pi)] root-val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize TreeSize(root);int* a (int*)malloc(sizeof(int)*(*returnSize));int i 0;postOrder(root, a, i);return a;
}
7. 另一颗树的子树
OJ链接--572. 另一棵树的子树 - 力扣LeetCode
题目描述:
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 示例 1 输入root [3,4,5,1,2], subRoot [4,1,2]
输出true示例 2 输入root [3,4,5,1,2,null,null,null,null,0], subRoot [4,1,2]
输出false提示
root 树上的节点数量范围是 [1, 2000]subRoot 树上的节点数量范围是 [1, 1000]-104 root.val 104-104 subRoot.val 104
分析: 遍历root树,找到root的所有子树与subroot树进行比较 代码展示: 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);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root NULL)return false;if(root-val subRoot-val isSameTree(root, subRoot))return true;return isSubtree(root-left,subRoot) || isSubtree(root-right, subRoot);
} 注意:这里需要用到我们之前已经解决的相同的树的问题 该函数用来判断二叉树 subRoot 是否是二叉树 root 的子树。 逻辑解释 空树检查 if(root NULL) return false; 如果 root 是空树直接返回 false因为空树不可能包含任何非空子树。 根节点值比较及完整树比较 if(root-val subRoot-val isSameTree(root, subRoot)) return true; 如果 root 的当前节点值与 subRoot 的根节点值相同并且 root 从当前节点开始的子树与 subRoot 完全相同通过调用 isSameTree 函数进行判断则返回 true。 递归检查左右子树 return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot); 如果上述条件都不满足则递归地检查 root 的左子树和右子树看其中是否存在与 subRoot 相同的子树。如果任意一个子树包含 subRoot返回 true。 总结 这两个函数结合起来可以有效地判断一棵二叉树是否是另一棵二叉树的子树。具体步骤如下 使用 isSubtree 函数遍历 root 的每个节点。对于每个节点检查该节点开始的子树是否与 subRoot 完全相同。如果找到一个与 subRoot 相同的子树立即返回 true。如果没有找到继续遍历 root 的左右子树直到所有节点都检查完毕。 这种方法通过递归遍历和子树比较确保准确判断子树关系。
