二叉树OJ淬体
例1：单值二叉树
题目
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 BinaryTreeNode { struct 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; }
