#yyds干货盘点#算法给小码农二叉树OJ淬体 _二叉

识字粗堪供赋役，不须辛苦慕公卿。这篇文章主要讲述#yyds干货盘点#算法给小码农二叉树OJ淬体相关的知识，希望能为你提供帮助。
二叉树OJ淬体例1：单值二叉树题目

文章图片

【#yyds干货盘点#算法给小码农二叉树OJ淬体】

文章图片

bool isUnivalTree(struct TreeNode* root) //空树直接就是单值 if(!root) 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：二叉树的前序遍历题目

文章图片

//我们先把二叉树的节点个数求出来 int BinaryTreeSize(struct TreeNode* root)return root == NULL ? 0 : BinaryTreeSize(root-> left)+BinaryTreeSize(root-> right)+1; void _preorderTraversal(struct TreeNode* root,int* a,int* i)if(!root) return; a[(*i)++] = root-> val; _preorderTraversal(root-> left,a,i); _preorderTraversal(root-> right,a,i); int* preorderTraversal(struct TreeNode* root, int* returnSize) //我们知道二叉树节点个数就好开辟数组大小了 int size =BinaryTreeSize(root); int* a = (int*)malloc(sizeof(int)*size); //我们直接递归preorderTraversal它，是不好递归的因为每次递归你都开辟一个数组吗，不现实 //我们应该递归他的类似性质的函数，不过不可以次次开辟数组，应该传递数组再给一个下标 int i = 0; _preorderTraversal(root,a,& i); *returnSize = size; return a;

例3：二叉树的中序遍历题目

文章图片

//二叉树节点个数函数 int BinaryTreeSize(struct TreeNode* root) if(!root) return 0; return BinaryTreeSize(root-> left)+BinaryTreeSize(root-> right)+1; //子函数 void _inorderTraversal(struct TreeNode* root,int* a,int* pi) if(!root) return; _inorderTraversal(root-> left,a,pi); a[(*pi)++] = root-> val; _inorderTraversal(root-> right,a,pi); int* inorderTraversal(struct TreeNode* root, int* returnSize) //把节点个数赋给数组大小 int size = BinaryTreeSize(root); //创建合适的数组 int* a = (int*)malloc(sizeof(int)*size); int i = 0; _inorderTraversal(root,a,& i); *returnSize = size; return a;

例4：二叉树的后序遍历题目

文章图片

//二叉树 int BinaryTreeSize(struct TreeNode* root) return root == NULL ? 0 : BinaryTreeSize(root-> left)+BinaryTreeSize(root-> right)+1; //子函数 void _postorderTraversal(struct TreeNode* root,int* a,int* pi) if(!root) return; _postorderTraversal(root-> left,a,pi); _postorderTraversal(root-> right,a,pi); a[(*pi)++] = root-> val; int* postorderTraversal(struct TreeNode* root, int* returnSize) //数组大小传过来 int size = BinaryTreeSize(root); //创建合适的数组 int* a = (int*)malloc(sizeof(int)*size); int i = 0; _postorderTraversal(root,a,& i); *returnSize = size; return a;

例5：相同的树题目

文章图片

bool isSameTree(struct TreeNode* p, struct TreeNode* q) //都为空 if(!p & & !q) return true; //有且只有一个是空 if(!p || !q) return false; //没有空树 if(p-> val != q-> val) return false; return isSameTree(p-> left,q-> left) & & isSameTree(p-> right,q-> right);

例6：对称二叉树题目

文章图片

bool _isSymmetricTree(struct TreeNode* root1,struct TreeNode* root2)//两个都是空就返回真 if(!root1 & & !root2) return true; //只有一个空直接假 if(!root1 || !root2) return false; if(root1-> val != root2-> val) return false; return _isSymmetricTree(root1-> left,root2-> right) & & _isSymmetricTree(root1-> right,root2-> left); bool isSymmetric(struct TreeNode* root) //空树就是对称 if(!root) return true; //返回他们判断结果 return _isSymmetricTree(root-> left,root-> right);

例7：另一棵树的子树题目

文章图片

//判断是否是相同的树 bool isSameTree(struct TreeNode* p, struct TreeNode* q) //都为空 if(!p & & !q) return true; //有且只有一个是空 if(!p || !q) 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) return false; if(isSameTree(root,subRoot)) return true; return isSubtree(root-> left,subRoot) || isSubtree(root-> right,subRoot);

例8：二叉树遍历题目

文章图片

#include < stdio.h> #include < stdlib.h> //树节点 typedef struct BinaryTreeNodestruct BinaryTreeNode* right; struct BinaryTreeNode* left; int val; BTNode; //创建树 BTNode* CreateTree(char* str,int* pi)//#就返回空 if(str[*pi] == #)(*pi)++; return NULL; //不是空开始建树 BTNode* root = (BTNode*)malloc(sizeof(BTNode)); root-> val = str[(*pi)++]; //递归创建 root-> right = CreateTree(str,pi); root-> left = CreateTree(str,pi); return root; //中序遍历 void InOrder(BTNode* root)//空就返回 if(!root) return; //先走左 InOrder(root-> right); //打印中 printf("%c ",root-> val); //再走右 InOrder(root-> left); int main()//因为不超过100 char str[100] = 0; //多组输入 while(scanf("%s",str) != EOF)//创建树 int i = 0; BTNode* root = CreateTree(str,& i); InOrder(root); return 0;