文章目录
- 前言
- 一、单值二叉树
- 二、相同的树
- 三、二叉树的前序遍历
- 四、二叉树的中序遍历
- 五、二叉树的后序遍历
- 六、另一棵树的子树
- 七、二叉树的遍历
- 八、 对称二叉树
- 总结
前言
leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍
一、单值二叉树
leetcode原题： 单值二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isUnivalTree(struct TreeNode* root) {
if(root == NULL)
return true;
if(root->left != NULL && root->left->val != root->val )
return false;
if(root->right != NULL && root->right->val != root->val)
return false;
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
- 递归思想：
- 每个节点都分别与它的左子树根节点和右子树根节点比较。
- 若传入的节点为NULL，返回 true。（不违反相同的规则）
- 若左右子树分别不为空并且分别不等于根节点则返回 false。
二、相同的树
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(p == NULL && q== NULL)
{
return true;
}
if(p == NULL && q != NULL || p != NULL && q == NULL)
{
return false;
}
if(p->val != q->val)
{
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
- 递归思想：
- 两棵树同时按照根节点，左子树，右子树的顺序比较每个节点。
- 若两个树根节点都为NULL，则返回true。
- 若两棵树根节点只有一个为NULL，则返回false。
- 若两棵树根节点的值不相等，则返回false。
三、二叉树的前序遍历
leetcode原题： 二叉树的前序遍历
- 其中returnSize是数组元素的个数。传入的是数组元素个数的指针。
- 要求返回一个数组。
/**
* 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().
*/
int TreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void preorder(struct TreeNode* root, int* a, int* pi)
{
if(root == NULL)
return;
a[(*pi)++] = root->val;
preorder(root->left, a, pi);
preorder(root->right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = TreeSize(root);
int* a = (int*)malloc(*returnSize * sizeof(int));
int i = 0;
preorder(root, a, &i);
return a;
}
- 思想：
- 先求出这个树的节点个数，赋值给returnSize。
- 动态申请returnSize个空间，同时定义下标变量。
- 在函数preorder中采用前序遍历，将每个节点的值依次赋值给数组。
四、二叉树的中序遍历
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().
*/
int TreeSize(struct TreeNode* root)
{
return root == NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void inorder(struct TreeNode* root, int* a, int* pi)
{
if(root == NULL)
return;
inorder(root->left, a, pi);
a[(*pi)++] = root->val;
inorder(root->right, a, pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = TreeSize(root);
int* a = (int*)malloc(*returnSize * sizeof(int));
int i = 0;
inorder(root, a, &i);
return a;
}
五、二叉树的后序遍历
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().
*/
int TreeSize(struct TreeNode* root)
{
return root==NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void postorder(struct TreeNode* root, int* a, int* pi)
{
if(root == NULL)
return;
postorder(root->left, a, pi);
postorder(root->right, a, pi);
a[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = TreeSize(root);
int* a = (int*)malloc(*returnSize * sizeof(int));
int i = 0;
postorder(root, a, &i);
return a;
}
六、另一棵树的子树
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(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(root == NULL)
return false;
if(isSameTree(root, subRoot))
{
return true;
}
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
- 将原二叉树与给定子树进行比较。
- 若相同返回true。
- 若不同，原二叉树的左子树和右子树分别与给定子树比较。有一个相同则返回true。
七、二叉树的遍历
牛客网原题: 二叉树的遍历
#include <stdio.h>
#include <stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
} BTNode;
BTNode* preorder(char* arr, int* pi)
{
if(arr[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->val = arr[(*pi)++];
root->left = preorder(arr, pi);
root->right = preorder(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] = {0};
scanf("%s", arr);
int i = 0;
BTNode* root = preorder(arr, &i);
Inorder(root);
return 0;
}
八、 对称二叉树
leetcode原题： 对称二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool order(struct TreeNode* lret, struct TreeNode* rret)
{
if(lret == NULL && rret == NULL)
return true;
if(lret == NULL || rret == NULL)
return false;
if(lret->val != rret->val)
return false;
return order(lret->left, rret->right) && order(lret->right, rret->left);
}
bool isSymmetric(struct TreeNode* root) {
if(root == NULL)
return true;
return order(root->left, root->right);
}
- 如若传入根节点是空树，则返回true。
- 若不是空树，比较它的左右子树。
-
- 若左右子树都是空，则返回true。
-
- 若左右子树只有一个是空，则返回false。
- 然后判断当前两个树节点的val是否相等，若不相等返回false。
- 若相等继续找子树。
总结
leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍
