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

leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历等的介绍

news 来源：原创 2024/9/28 23:32:10

文章目录

前言
一、单值二叉树
二、相同的树
三、二叉树的前序遍历
四、二叉树的中序遍历
五、二叉树的后序遍历
六、另一棵树的子树
七、二叉树的遍历
总结

前言

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;
}