室友不在家，打开LeetCode来一次题库屠杀.手把手带你刷二叉树基础OJ题，请不要学得太激烈.

叮叮叮当QQ响起会是谁呢
NaYo

文章目录

🍭1.单值二叉树

题目链接

🍒1.1题目描述

🍀1.2 思路

如果根是空，那么

return true;

如果根不是空，那我们再继续比较根和它的左子树、右子树。注意不要比较相等，因为相等并不能得到结果，并不能说明树是单值二叉树，还要继续递归往下走。如果每个根和它的左右孩子都相等，说明这是一颗单值二叉树。

🍉1.3 代码演示

bool isUnivalTree(structTreeNode* root){if(root ==NULL)return true;if(root->left && root->val != root->left->val)return false;if(root->right && root->val != root->right->val)return false;returnisUnivalTree(root->left)&&isUnivalTree(root->right);}

🍭2.相同的树

题目链接

🍒2.1题目描述

🍀2.2 思路

一棵树分成三个部分进行比较：根、左子树、右子树。左右子树又可以分为根、左子树、右子树。直到NULL结束。

🍉2.3 代码演示

bool isSameTree(structTreeNode* p,structTreeNode* q){//都是空树if(p==NULL&&q==NULL)return true;//一个为空，一个不为空if(p==NULL||q==NULL)return false;//都不为空if(p->val != q->val)return false;//递归比较左右子树returnisSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}

🍭3.对称二叉树

题目链接

🍒3.1题目描述

🍀3.2 思路

没有必要比较根，我的左子树和你的右子树进行比较，我的右子树和你的左子树进行比较。写一个_isSymmetric子函数来比较。

🍉3.3 代码演示

bool _isSymmetric(structTreeNode*p,structTreeNode*q){if(p==NULL&& q==NULL)return true;if(p==NULL||q==NULL)return false;return p->val==q->val
    &&_isSymmetric(p->left,q->right)&&_isSymmetric(p->right,q->left);}

bool isSymmetric(structTreeNode* root){if(root==NULL)return true;return_isSymmetric(root->left,root->right);}

🍭4.二叉树的前序遍历

题目描述

🍒4.1题目描述

🍀4.2 思路

return一个前序遍历的数组，且这个数组必须是被malloc的。

1. 写一个TreeSize先来计算二叉树的大小
2. 写一个_preorder来实现前序遍历，并把前序遍历的结果存在一个数组里

int *pi, int *returnSize为输出型参数。

🍉4.3 代码演示

intTreeSize(structTreeNode* root){return root ==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;}void_preorder(structTreeNode* 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(structTreeNode* root,int* returnSize){int size=TreeSize(root);int*a =malloc(sizeof(int)*size);*returnSize = size;int i =0;_preorder(root,a,&i);return a;}

🍭5.二叉树的中序遍历

题目链接

🍒5.1题目描述

🍀5.2 思路

return一个中序遍历的数组，且这个数组必须是被malloc的。

1. 写一个TreeSize先来计算二叉树的大小
2. 写一个_inorder来实现前序遍历，并把中序遍历的结果存在一个数组里

int *pi, int *returnSize为输出型参数。

🍉5.3 代码演示

intTreeSize(structTreeNode* root){return root ==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;}void_inorder(structTreeNode* 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(structTreeNode* root,int* returnSize){int size=TreeSize(root);int*a =malloc(sizeof(int)*size);*returnSize = size;int i =0;_inorder(root,a,&i);return a;}

🍭6.二叉树的后序遍历

题目描述

🍒6.1题目描述

🍀6.2 思路

return一个后序遍历的数组，且这个数组必须是被malloc的。

1. 写一个TreeSize先来计算二叉树的大小
2. 写一个_postorder来实现前序遍历，并把后序遍历的结果存在一个数组里

int *pi, int *returnSize为输出型参数。

🍉6.3 代码演示

intTreeSize(structTreeNode* root){return root ==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;}void_postorder(structTreeNode* 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(structTreeNode* root,int* returnSize){int size=TreeSize(root);int*a =malloc(sizeof(int)*size);*returnSize = size;int i =0;_postorder(root,a,&i);return a;}

🍭7.另一颗树的子树

题目链接

🍒7.1题目描述

🍀7.2 思路

左边树中每一颗子树都比较一下isSameTree。
遍历树，树中每个节点所在的子树，都跟subRoot进行一下比较即可。

🍉7.3 代码演示

bool isSameTree(structTreeNode* p,structTreeNode* q){//都是空树if(p==NULL&&q==NULL)return true;//一个为空，一个不为空if(p==NULL||q==NULL)return false;//都不为空if(p->val != q->val)return false;//递归比较左右子树returnisSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}

bool isSubtree(structTreeNode* root,structTreeNode* subRoot){if(root==NULL)return false;returnisSameTree(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);}

❤️8.总结

觉得有收获的话，一键三连支持博主哦