目录
一、相同的树
二、单值二叉树
三、对称二叉树
四、树的遍历
前序遍历
中序遍历
后序遍历
五、另一颗树的子树
六、二叉树的遍历
七、翻转二叉树
八、平衡二叉树
一、相同的树
链接:100. 相同的树 – 力扣(LeetCode)
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);}
- 首先考虑比较时节点为空的情况,当比较到二者节点都为空时,则当前二者节点相同,返回true。
- 二者节点只有一个为空时,当前二者节点不相同,返回false。
- 然后考虑不为空时,判断二者的值是否相等,不相等返回false。
- 最后递归调用比较二者当前节点的左子树和右子树,都为true则返回true。
二、单值二叉树
链接:965. 单值二叉树 – 力扣(LeetCode)
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->left) &&isUnivalTree(root->right);}
- 首先判断当前节点是否为空,如果为空则返回true。
- 如果当前节点不为空,则判断其左右子树的值是否与当前节点的值相同,如果不同则返回false。
- 如果左右子树的值都与当前节点的值相同,则递归判断左右子树是否为同值二叉树,即左右子树的所有节点的值都相同。
- 这个递归过程会一直往下遍历到叶子节点,如果所有节点的值都相同,则返回true,否则返回false。
三、对称二叉树
思路:左子树的左节点与右子树的右节点比较,左子树的右节点和右子树的左节点比较
bool _isSymmetric(struct TreeNode* leftRoot, struct TreeNode* rightRoot) {if (leftRoot == NULL && rightRoot == NULL)return true;if (leftRoot == NULL || rightRoot == NULL)return false;if (leftRoot->val != rightRoot->val)return false;return _isSymmetric(leftRoot->left, rightRoot->right) && _isSymmetric(leftRoot->right, rightRoot->left);}bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root->left, root->right);}
OJ是允许我们额外根据需要创建函数的,原函数的参数只有一个,不能满足同时判断两个节点的是否相等的要求,所以我们创建递归函数_isSymmetric(),用来判断左右子树是否对称。
- 如果左右子树都为空,说明对称,返回true;
- 如果左右子树只有一个为空,说明不对称,返回false;
- 如果左右子树的值不相等,说明不对称,返回false;
- 否则,递归判断左子树的左子树和右子树的右子树是否对称,以及左子树的右子树和右子树的左子树是否对称,如果都对称,返回true,否则返回false。
- 函数isSymmetric()则是调用_isSymmetric()函数,传入根节点的左子树和右子树,判断整个二叉树是否对称。
四、树的遍历
前序遍历
链接:144. 二叉树的前序遍历 – 力扣(LeetCode)
int TreeSize(struct TreeNode* root) {return root == NULL " />中序遍历 94. 二叉树的中序遍历 - 力扣(LeetCode)
int TreeSize(struct TreeNode* root) {return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;}void _inorder(struct TreeNode* root, int* a, int* i) {if (root == NULL)return;_inorder(root->left, a, i);a[(*i)++] = root->val;_inorder(root->right, a, i);}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;}
后序遍历
145. 二叉树的后序遍历 - 力扣(LeetCode)
int TreeSize(struct TreeNode* root) {return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;}void _postorder(struct TreeNode* root, int* a, int* i) {if (root == NULL)return;_postorder(root->left, a, i);_postorder(root->right, a, i);a[(*i)++] = 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;}
五、另一颗树的子树
链接:572. 另一棵树的子树 - 力扣(LeetCode)
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);}
调用 isSameTree 辅助判断子树是否相等:
- 首先考虑比较时节点为空的情况,当比较到二者节点都为空时,则当前二者节点相同,返回true。
- 二者节点只有一个为空时,当前二者节点不相同,返回false。
- 然后考虑不为空时,判断二者的值是否相等,不相等返回false。
- 最后递归调用比较二者当前节点的左子树和右子树,都为true则返回true。
isSubtree函数:
- 如果
root
是NULL
,那么它不可能包含任何子树,函数返回false
。 - 如果
isSameTree(root, subRoot)
返回true
,说明在当前的节点上,root
和subRoot
完全相同,那么subRoot
当然是root
的子树,函数返回true
。 - 如果当前节点不匹配,那么递归地在
root
的左子树和右子树中查找subRoot
。 - 如果
subRoot
是root
左子树或右子树的子树,函数就返回true
。
六、二叉树的遍历
链接:二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
我们需要根据给出的先序(前序)遍历反推出树的样子,例如下图,我们可以动手试一试:
好的,如果你已经熟悉如何根据遍历反推二叉树的形状,那么试着推出题中的遍历的吧。
注意:这道题需要写出主函数,并不像力扣提供接口。
首先我需要创建二叉树的结构体和相关函数:
#include #include typedef int BTDataType;typedef struct BinaryTreeNode{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;BTNode* BuyNode(BTDataType x){BTNode* node=(BTNode*)malloc(sizeof(BTNode));if(node==NULL){perror("malloc fail");return NULL;}node->data=x;node->left=node->right=NULL;return node;}
然后进行二叉树的创建:
- 该函数接收两个参数,一个是字符串a,另一个是指向整型变量i的指针,用于记录当前处理到字符串a的哪个位置。
- 当前位置数组元素为 # 表示元素值为空,更新数组索引到下一个位置,返回NULL
- 当前位置元素不为空则为其开辟空间,为树创建新节点,更新数组索引到下一个位置。
- 递归调用CreateTree函数分别创建该节点的左右子树。
- 最后返回该节点的指针。
在main函数中:
- 先定义了一个字符数组a,用于存储输入的字符串,
- 然后调用CreateTree函数创建二叉树,将根节点的指针赋值给root,
- 最后调用InOrder函数对二叉树进行中序遍历,并输出换行符。
BTNode* CreateTree(char* a,int* i){if(a[*i]=='#'){(*i)++;return NULL;}BTNode* root=BuyNode(a[*i]);(*i)++;root->left=CreateTree(a, i);root->right=CreateTree(a, i);return root;}void InOrder(BTNode* root){if(root==NULL)return;InOrder(root->left);printf("%c ",root->data);InOrder(root->right);}int main() {char a[1000];scanf("%s",a);int i=0;BTNode* root=CreateTree(a,&i);InOrder(root);printf("\n");return 0;}
七、翻转二叉树
链接:226. 翻转二叉树 - 力扣(LeetCode)
truct TreeNode* invertTree(struct TreeNode* root) {if(root==NULL)return NULL;struct TreeNode* left=invertTree(root->left);struct TreeNode* right=invertTree(root->right);root->left=right;root->right=left;return root;}
- 如果当前节点为空,则返回NULL.
- 否则,递归调用函数对左右子树进行处理,递归到二叉树最底部,从最底部往上进行翻转。
- 将节点的左节点赋值为右节点,右节点赋值为左节点,
- 最后返回根节点。
八、平衡二叉树
链接:110. 平衡二叉树 - 力扣(LeetCode)
第一种:求出左右子树高度进行判断比较。
height函数用于计算二叉树的高度,它采用递归的方式计算左右子树的高度,然后返回左右子树高度的较大值加1,表示当前节点的高度。
isBalanced函数则是用于判断二叉树是否平衡,它首先判断当前节点是否为空,如果为空则返回true,否则通过 abs 函数计算左右子树的高度差的绝对值,如果高度差大于1,则返回false,否则递归判断左右子树是否平衡。
int height(struct TreeNode* root){ if(root == NULL)return 0;int leftHeight = height(root->left);int rightHeight = height(root->right);return leftHeight > rightHeight " />int maxDepth(struct TreeNode* root){return root ? 1 + fmax(maxDepth(root->left) , maxDepth(root->right)) : 0;}bool isBalanced(struct TreeNode* root){if(root == NULL)return true;int left = maxDepth(root->left);int right = maxDepth(root->right);return abs(left - right) left)&& isBalanced(root->right);}