【LeetCode】——链式二叉树经典OJ题详解

=========================================================================

主页点击直达：个人主页

我的小仓库：代码仓库

C语言偷着笑：C语言专栏

数据结构挨打小记：初阶数据结构专栏

Linux被操作记：Linux专栏

LeetCode刷题掉发记：LeetCode刷题

算法头疼记：算法专栏

=========================================================================

前言：

LeetCode 965.单值二叉树

LeetCode 100.相同的树

LeetCode 101.对称二叉树

LeetCode 144 145 94 .二叉树的前、中、后序遍历

LeetCode 572.另一棵树的子树

前言：

在之前的文章讲解了二叉树的链式结构的实现以及前、中、后序的遍历。不知道大家看完后有没有理解和有所收获，今天基于那篇文章给大家分享讲解几道经典的题目，更便于大家的理解和深入。

二叉树的题目一定要会两个思想：

第一个思想：拆分一定要将二叉树拆分为根、左子树、右子树首先就是要判断根结点是否为空。第二个思想：递归，善于使用递归。

LeetCode 965.单值二叉树

OJ链接

题目描述：

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例 1：
输入：[1,1,1,1,1,null,1]
输出：true
示例 2：
输入：[2,2,2,5,2]
输出：false
审题总结：

判断一个二叉树这所有节点的值是否相等，相等返回true，否则返回false；

思路讲解：首先判断根是否为空，如果为空直接返回true。不为空判断左子树是否存在，存在的话判断和根节点的值是否相等，如果相等返回true，否则返回false；继续判断右子树是否存在，存在的话判断和根节点的值是否相等，如果相等返回true，否则返回法false。左右子树都存在的话使用递归遍历。

接口代码
bool isUnivalTree(struct TreeNode* 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;return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

LeetCode 100.相同的树

OJ链接

题目描述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
思路讲解：

先将根拆结点拆分出来，两个根节点有三种情况，都为空、两个根节点中有一个为空。如果都为空，则返回true；如果有一个为空则返回false。根节点判断完成后判断根节点的值是否相等；使用递归遍历左子树和右子树。

接口代码
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);
}

LeetCode 101.对称二叉树

OJ链接

题目描述：

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：falses
思路讲解：

这个题目和上个题目非常的相似，还是拆分为根、左子树、右子树。这里将两个子树看成单独的树，就和上面题的思路大差不差了。不同的是要判断左边的值和右边的值是否相等，这样才算对称。

实现代码
 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->right)&&isSameTree(p->right,q->left);}
bool isSymmetric(struct TreeNode* root){if(root!=NULL){return isSameTree(root->left,root->right);}elsereturn true;
}

LeetCode 144 145 94 .二叉树的前、中、后序遍历

前序遍历OJ链接

中序遍历OJ链接

后序遍历OJ链接

关于二叉树的前、中、后序遍历的文章点击直达，这里我不做介绍。由于这三个题目是差不多只是将遍历的值用数组的形式便是出来，所以我就只讲解前序遍历、中、后序遍历交给大家练习。

题目描述：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
思路讲解：

首先求出这棵二叉树有几个结点，根据结点动态开辟相应大小的空间。将根节点、动态开辟的数组，变量的地址，交给一个前序遍历的函数，根据前序遍历的规则，进行递归给数组赋值。

实现代码
 int treesize(struct TreeNode*root){return root==NULL? 0:treesize(root->left)+treesize(root->right)+1;}void preoder(struct TreeNode *root,int *a,int *pi){if(root==NULL)return;a[(*pi)++]=root->val;preoder(root->left,a,pi);preoder(root->right,a,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize){int n=treesize(root);int *a=(int *)malloc(sizeof(int )*n);int j=0;preoder(root,a,&j);*returnSize=n;return a;
}

LeetCode 572.另一棵树的子树

OJ链接

题目描述：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：falses
思路讲解：

这个题和上面的LeetCode 100.相同的树基本上也大差不差。首先判断根节点是否为空，如果根节点为空，则直接返回false；不为空则直接使用是否为相同的树判断函数，判断所给树是否为子树，如果为真则直接返回true，使用递归遍历根节点的左右子树和所给所给子树相比较。

实现代码
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(root->val==subRoot->val)
{if(isSameTree(root,subRoot))return true;
}
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);}