玉林建设信息网站免费个人网站制作设计

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

玉林建设信息网站,免费个人网站制作设计,建盏生态公司,做相似网站目录 二叉树OJ(leetcode)训练习题#xff1a;#xff1a; 1.单值二叉树 2.检查两棵树是否相同 3.二叉树的前序遍历 4.另一棵树的子树 5.二叉树的构建及遍历 6.二叉树的销毁 7.判断二叉树是否是完全二叉树 二叉树OJ(leetcode)训练习题#xff1a;#xff1a; 1.单值二叉…目录 二叉树OJ(leetcode)训练习题 1.单值二叉树 2.检查两棵树是否相同  3.二叉树的前序遍历 4.另一棵树的子树 5.二叉树的构建及遍历 6.二叉树的销毁 7.判断二叉树是否是完全二叉树  二叉树OJ(leetcode)训练习题 1.单值二叉树 //单值二叉树 //思路:相等的传递性 struct TreeNode {int val;struct TreeNode* left;struct TreeNode* right; }; 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); } 2.检查两棵树是否相同  //相同的树 //思路:根比较 子树比较 struct TreeNode {int val;struct TreeNode* left;struct TreeNode* right; }; 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;//走到此位置说明p,q均不为空且根的值是相等的return isSameTree(p-left, q-right) isSameTree(p-right, q-right); } 3.二叉树的前序遍历 //二叉树的前序遍历 //要求:既要返回数组的首地址 又要返回数组的长度 struct TreeNode {int val;struct TreeNode* left;struct TreeNode* right; }; int TreeSize(struct TreeNode* root) {if (root NULL)return 0;return TreeSize(root-left) TreeSize(root-right) 1; } void preorder(struct TreeNode* root, int* a, int* pi) {if (root NULL)return;a[*pi] root-val;(pi);preorder(root-left, a, pi);preorder(root-right, a, pi); } int preorderTraversal(struct TreeNode* root, int* returnSize) {int n TreeSize(root);int* a (int*)malloc(sizeof(int) * n);int i 0;preorder(root, a, i);returnSize n;return a; } 4.另一棵树的子树  //另一棵树的子树 //思路:原树中的每棵子树都和subRoot树比较相同的树代码 struct TreeNode {int val;struct TreeNode left;struct TreeNode* right; }; 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;//走到此位置说明p,q均不为空且根的值是相等的return isSameTree(p-left, q-right) 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); } 5.二叉树的构建及遍历 //二叉树遍历 //通过前序遍历的数组构建二叉树 typedef char BTDataType; typedef struct BinaryTreeNode {BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right; }BTNode; //递归的下一层在返回时 不会影响上一层 所以要传地址 //注意:树的每个节点不是递归的时候链接上的 而是在返回的时候链接上的 root-left BinaryTreeCreate(a,pi) BTNode* BinaryTreeCreate(BTDataType* a, int* pi) {if (a[*pi] #){(pi);return NULL;}BTNode root (BTNode*)malloc(sizeof(BTNode));if (root NULL){perror(malloc fail);return NULL;}root-data a[*pi];(pi);root-left BinaryTreeCreate(a, pi);root-right BinaryTreeCreate(a, pi);return root; } void InOrder(BTNode root) {if (root NULL){return;}InOrder(root-left);printf(%c , root-data);InOrder(root-right); } 6.二叉树的销毁 //二叉树销毁 //外面调用该函数的人置空 void BinaryTreeDestory(BTNode* root) {if (root NULL){return;}BinaryTreeDestory(root-left);BinaryTreeDestory(root-right);free(root); } 7.判断二叉树是否是完全二叉树  //判断二叉树是否是完全二叉树 //思路:层序遍历一层一层走遇到空以后后续层序不能有非空有非空就不是完全二叉树 //注:完全二叉树遇到空以后 后面节点一定都入队列了 //复制粘贴队列代码 #pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h typedef int QDataType; typedef struct QueueNode {struct QueueNode* next;QDataType data; }QNode; //第三种不用二级指针的方式 封装成结构体 typedef struct Queue {QNode* head;QNode* tail;int size; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); //取队列头部数据 QDataType QueueFront(Queue* pq); //取队列尾部数据 QDataType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq); #includeQueue.h void QueueInit(Queue* pq) {assert(pq);pq-head pq-tail NULL;pq-size 0; } void QueueDestory(Queue* pq) {assert(pq);QNode* cur pq-head;while (cur){QNode* del cur;cur cur-next;free(del);}pq-head pq-tail NULL; } void QueuePush(Queue* pq, QDataType x) {assert(pq);QNode* newnode (QNode)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}else{newnode-data x;newnode-next NULL;}if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size; } void QueuePop(Queue pq) {assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* del pq-head;pq-head pq-head-next;free(del);del NULL;}pq-size–; } //取队列头部数据 QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-head-data; } //取队列尾部数据 QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-tail-data; } bool QueueEmpty(Queue* pq) {assert(pq);return pq-head NULL pq-tail NULL; } int QueueSize(Queue* pq) {assert(pq);/QNode cur pq-head;int n 0;while (cur){n;cur cur-next;}return n;/return pq-size; } int BinaryTreeComplete(BTNode root) {Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL){break;}QueuePush(q, front-left);QueuePush(q, front-right);}//遇到空以后 后面全是空 则是完全二叉树//遇到空以后 后面存在非空 则不是完全二叉树while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front ! NULL){QueueDestory(q);return false;}}QueueDestory(q);return true; }