二叉树OJ题（内含链接以及解答）

单值二叉树

. - 力扣（LeetCode）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/typedef struct TreeNode TreeNode;
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->right) && isUnivalTree(root->left);
}

相同的树

. - 力扣（LeetCode）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/typedef struct TreeNode TreeNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//都为空if(q == NULL && p == 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);
}

 对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/typedef struct TreeNode TreeNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//都为空if(q == NULL  && p == 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);
}

另一棵树的子树 

. - 力扣（LeetCode）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//都为空if(q == NULL && p == 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(isSameTree(root,subRoot)){return true;}return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

二叉树前序遍历 

. - 力扣（LeetCode）

/*** 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().*/
typedef struct TreeNode TreeNode;int Treesize(TreeNode *root){if(root == NULL){return 0;}return 1 + Treesize(root->left) + Treesize(root->right);}
void _preorderTraversal(TreeNode* root,int* arr,int *pi){if(root == NULL){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* arr =(int*) malloc(sizeof(int) * (*returnSize));int i = 0;_preorderTraversal(root,arr,&i);return arr;
}

中序遍历以及后序遍历链接如下：其解答过程同前序遍历几乎一模一样

中序遍历         . - 力扣（LeetCode）

后序遍历         . - 力扣（LeetCode）

二叉树的遍历

二叉树遍历_牛客题霸_牛客网

#include <stdio.h>typedef struct BinaryTreeNode
{char val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->val = x;newnode->right = newnode->left = NULL;return newnode;
}
BTNode* createTree(char* arr,int*pi)
{if(arr[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = BuyNode(arr[(*pi)++]);root->left = createTree(arr, pi);root->right = createTree(arr, pi);return root;
}void INOrder(BTNode * root)
{if(root == NULL){return;}INOrder(root->left);printf("%c ",root->val);INOrder(root->right);
}
int main() {char arr[100];scanf("%s",arr);int pi = 0;BTNode* root = createTree(arr,&pi);INOrder(root);return 0;
}