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

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

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


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


LeetCode 965.单值二叉树

OJ链接

题目描述:

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


示例 1:1603b81d6ccf36705808583563d55298.png



输入:[1,1,1,1,1,null,1]

输出:true

示例 2:3da4c67ca39c97da4a33d217a5097d68.png



输入:[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:

3b8b02406804fbab1d1cb767fc194115.jpg


输入:p = [1,2,3], q = [1,2,3]

输出:true

示例 2:


adf74d11db93e96630d148752c538d98.jpg

输入:p = [1,2], q = [1,null,2]

输出:false

示例 3:

262e2bcc6236441546307fa888c6fdf6.jpg


输入: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:


7e75bf55adf49a117c078dc0d6b109e4.jpg

输入:root = [1,2,2,3,4,4,3]

输出:true

示例 2:

0ddb71192c4d6612fafc40d7c3345ba0.jpg


输入: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);
 }
 else
 return true;
}


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

前序遍历OJ链接

中序遍历OJ链接

后序遍历OJ链接


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

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


示例 1:

77bb92645cdf178d221cb2fc71e4525c.jpg


输入: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:

b5cfa2d792b44f0c24afef68d8492a17.jpg


输入:root = [3,4,5,1,2], subRoot = [4,1,2]

输出:true

示例 2:

c8f3dc38442e4b0d9df2e617b955a84c.jpg

输入: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);
}


相关文章
|
13天前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
27 6
|
3天前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
|
3天前
|
算法 Java
LeetCode第94题二叉树的中序遍历
文章介绍了LeetCode第94题"二叉树的中序遍历"的解法,使用递归实现了中序遍历的过程,遵循了"左根右"的遍历顺序,并提供了清晰的Java代码实现。
LeetCode第94题二叉树的中序遍历
|
13天前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
15 7
|
13天前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - II. 从上到下打印二叉树 II
本文提供了一种Python实现方法,用于层次遍历二叉树并按层打印结果,每层节点按从左到右的顺序排列,每层打印到一行。
24 3
|
13天前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - I. 从上到下打印二叉树
本文介绍了使用Python实现从上到下打印二叉树的解决方案,采用层次遍历的方法,利用队列进行节点的访问。
20 2
|
14天前
|
Python
【Leetcode刷题Python】257. 二叉树的所有路径
LeetCode第257题"二叉树的所有路径"的Python语言解决方案,通过深度优先搜索算法来找到并返回所有从根节点到叶子节点的路径。
13 2
|
14天前
|
Python
【Leetcode刷题Python】111. 二叉树的最小深度
LeetCode第111题"二叉树的最小深度"的Python语言解决方案,通过递归计算从根节点到最近叶子节点的最短路径上的节点数量。
9 2
|
11天前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
29 0
|
11天前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
22 0