【二叉树】—— 算法题

一、单值二叉树题目要求判断二叉树是不是单值二叉树就是所以节点的值都相等。思路利用二叉树的递归思想判断每一个节点值与其左右子节点的值是否相等如果遇到空节点就返回true说明每一个节点值都相等如果遇到节点的值与其左右节点值不相等就返回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); }二、相同的树 — 对称二叉树 — 另一颗树的子树2.1、相同的树判断两个二叉树是否相等思路同时遍历两个二叉树如果遍历到两个二叉树节点同时为空就说明这两个二叉树相同如果其中一个为空而另一个不为空就说明两个二叉树不相同如果遍历过程中遇到两个二叉树节点的值不相等则两个二叉树不相同。简单分析一下同时遍历这两个二叉树两个二叉树节点都不为空且值相等继续遍历其左子树两个二叉树节点都不为空且值相等继续遍历其左子树两个二叉树节点都为空返回true先遍历二叉树是2节点的右节点也为空这里直接跳过了。这里回退到1这个节点接下来遍历1的右子树遍历到节点都不为空且值相等继续遍历 这因为3的左右节点都为空就一步带过遍历结束没有遇到一个节点为空一个节点不为空或者值不相等的情况就返回true。代码如下typedef struct TreeNode TreeNode; 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); }2.2、对称二叉树判断二叉树是否是对称二叉树这里还是实现与上题相同的树类似的思路。思路利用相同的树的方法判断二叉树根节点的左右子树是否对称判断对称直接判断一个节点的左子树和另一个节点的右子树是否相等即可。代码如下typedef struct TreeNode TreeNode; 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-right) isSameTree(p-right, q-left); } bool isSymmetric(struct TreeNode* root) { return isSameTree(root-left,root-right); }2.3、另一颗树的子树判断一个树是否是另一个树的子树思路还是利用相同二叉树的方法判断二叉树及其左右子树中是否存在与另一棵树相同的树。代码如下typedef struct TreeNode TreeNode; 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(rootNULL) { return false; } if(isSameTree(root,subRoot)) { return true; } return isSubtree(root-left,subRoot) ||isSubtree(root-right,subRoot); }三、二叉树的遍历前序、中序、后序本题要求前序遍历二叉树并且返回前序遍历的结果以数组方式返回并且还用通过指向修改数据个数。思路这里首先求二叉树的节点个数然后动态申请内存来存储数据并且用来最后返回数组首元素地址最后就是将数据存储到数组当中了使用前序遍历。代码如下typedef struct TreeNode TreeNode; int TreeSize(TreeNode* root) { if (root NULL) { return 0; } return TreeSize(root-left) TreeSize(root-right) 1; } void _preorderTraversal(TreeNode* root,int* arr,int* pi) { if(rootNULL) { return ; } arr[(*pi)]root-val; _preorderTraversal(root-left,arr,pi); _preorderTraversal(root-right,arr,pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { // 求出二叉树的节点个数 *returnSize TreeSize(root); // 动态申请空间大小 int* returnArr(int*)malloc(sizeof(int)*(*returnSize)); // 前序遍历 int i0; _preorderTraversal(root,returnArr,i); return returnArr; }中序和后序遍历与其思路一样这里直接看代码。中序遍历typedef struct TreeNode TreeNode; int TreeSize(TreeNode* root) { if (root NULL) { return 0; } return TreeSize(root-left) TreeSize(root-right) 1; } void _inorderTraversal(TreeNode* root,int* arr,int* pi) { if(rootNULL) { return ; } _inorderTraversal(root-left,arr,pi); arr[(*pi)]root-val; _inorderTraversal(root-right,arr,pi); } int* inorderTraversal(struct TreeNode* root, int* returnSize) { // 求出二叉树的节点个数 *returnSize TreeSize(root); // 动态申请空间大小 int* returnArr(int*)malloc(sizeof(int)*(*returnSize)); // 中序遍历 int i0; _inorderTraversal(root,returnArr,i); return returnArr; }后序遍历typedef struct TreeNode TreeNode; int TreeSize(TreeNode* root) { if (root NULL) { return 0; } return TreeSize(root-left) TreeSize(root-right) 1; } void _postorderTraversal(TreeNode* root,int* arr,int* pi) { if(rootNULL) { return ; } _postorderTraversal(root-left,arr,pi); _postorderTraversal(root-right,arr,pi); arr[(*pi)]root-val; } int* postorderTraversal(struct TreeNode* root, int* returnSize) { // 求出二叉树的节点个数 *returnSize TreeSize(root); // 动态申请空间大小 int* returnArr(int*)malloc(sizeof(int)*(*returnSize)); // 中序遍历 int i0; _postorderTraversal(root,returnArr,i); return returnArr; }四、二叉树的构建和遍历创建二叉树并且中序遍历。因为这里题目说先序遍历字符串我们根据这个来构建二叉树本题要求写全部代码。思路先创建字符数组根据输入的字符串进行创建二叉树创建完成以后再进行中序遍历输出即可。代码如下#include stdio.h #includestdlib.h typedef struct BinaryTreeNode { char str; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(char x) { BTNode* newnode(BTNode* )malloc(sizeof(BTNode)); newnode-strx; newnode-leftnewnode-rightNULL; return newnode; } BTNode* CreatTree(char* str,int* pi) { if(str[*pi]#) { (*pi); return NULL; } BTNode* rootBuyNode(str[(*pi)]); root-leftCreatTree(str,pi); root-rightCreatTree(str,pi); return root; } //中序遍历 void InOrder(BTNode* root) { if(rootNULL) { return; } InOrder(root-left); printf(%c ,root-str); InOrder(root-right); } int main() { char str[100]; scanf(%s,str); //根据字符创建二叉树 int i0; BTNode* rootCreatTree(str, i); InOrder(root); return 0; }感谢各位大佬支持并指出问题如果本篇内容对你有帮助可以一键三连支持以下感谢支持