江苏天宇建设集团官方网站,表白网站制作器,网站总体建设方面的优势与不足,苏州高端网站制作#x1f4d9;作者简介#xff1a; 清水加冰#xff0c;目前大二在读#xff0c;正在学习C/C、Python、操作系统、数据库等。 #x1f4d8;相关专栏#xff1a;C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 #x1f44d… 作者简介 清水加冰目前大二在读正在学习C/C、Python、操作系统、数据库等。 相关专栏C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 收藏 ⭐留言 如有错误还望各路大佬指正 ✨每一次努力都是一种收获每一次坚持都是一种成长✨ 目录 前言
题目1翻转二叉树
题目2相同的树
题目3对称二叉树
题目4另一棵树的子树 题目5二叉树的前序遍历
总结 前言 我们学习了二叉树的顺序结构和链式结构在日常刷题在我们最常见的就是链式二叉树刚学习完链式二叉树刷题上手比较难本期我将继续开始数据结构刷题专栏为大家提供二叉树初阶相关的练习和力扣OJ的经典题目以及题目讲解以便于大家更容易上手二叉树部分的刷题。 题目1翻转二叉树
题目描述 题目链接
翻转二叉树https://leetcode.cn/problems/invert-binary-tree/description/
✨题目解析 本道题目较为简单要学会巧妙运用递归解决问题翻转二叉树也就是翻转它的左子树和右子树然后不断的向下分在使用递归时要注意递归结束的条件确保所有的控件路径都返回值。 代码如下
struct TreeNode* invertTree(struct TreeNode* root){if(rootNULL){return NULL;}struct TreeNode* leftinvertTree(root-left);struct TreeNode* rightinvertTree(root-right); root-rightleft;root-leftright;return root;
}
题目2相同的树
题目描述 题目链接
相同的树https://leetcode.cn/problems/same-tree/description/
✨题目解析 这道题目的递归思路比上道题复杂一点主要考察的是对递归的使用以及控制。题目中传进来的是两个树那要如何去控制递归呢
两棵树是否相同主要就是比较对于位置的节点数据是否相同如果两棵树的每个对应节点都相等这两棵树就相等但单纯的判断值是否相等无法做到所有的控件路径都返回值这里也要考虑特殊情况当一颗树为NULL另一颗树不为空这时就要返回false两棵树当前节点都为NULL就返回true。有了这些前提我们对代码进行实现那这样写对不对呢
bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(pNULLqNULL)//两个都为NULL就返回True{return true;}if(pNULL||qNULL)//两棵树都不为NULL为前提{return false;}if(p-valq-val){return true;}return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
} 这样写乍一看没什么问题但它在力扣上通过不了例如
p[1,2] q[1,null,2] 你会发现它根本就没递归进去就返回了只比较了根节点的值。我们需要让它递归到最后也就是叶子节点从叶子节点开始。既然正向行不通那就逆向如果它们的val不相等就返回false。
bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(pNULLqNULL){return true;}if(pNULL||qNULL){return false;}if(p-val!q-val){return false;}return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}
这样就可以递归到叶子节点如果递归到最后一直到叶子节点都没有返回false那就说明递归路径上的节点都相等如果有一个返回的是false最后返回的是左子树与右子树取的结果最终一定会返回false。如果节点都相当才会返回true。
例如这棵树递归从左子树开始节点2的left递归返回trueright返回也是true那节点2整体返回就是true然后开始递归右子树右子树返回和左子树一样也是true。然后返回到节点1的递归左右子树都为true那整体就返回true。
题目3对称二叉树
题目描述 题目链接
对称二叉树https://leetcode.cn/problems/symmetric-tree/✨题目解析 这道题的解法和上道题很像也就是在上道题做了一点进阶。
它让我们判断对称那我们就可以将这棵树的左子树和右子树分为两棵树上道题目判断是相同位置的节点相同我们传的都是p-left,q-left我们观察一下对称的二叉树左子树的左孩子节点与右子树的右孩子节点相同左子树的右孩子与右子树的左孩子相同。 那我们在判断相同时是否就可以这样传值去比较左子树的左孩子和右子树的右孩子左子树的右孩子和右子树的左孩子是否相同。 那我们就只需改变一下传的参数即可。我们套用一下上边相同的二叉树的进行变形一下
bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(pNULLqNULL){return true;}if(pNULL||qNULL){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){return isSameTree(root-left,root-right);
} 题目4另一棵树的子树 题目链接
另一棵树的子树https://leetcode.cn/problems/subtree-of-another-tree/description/
✨题目解析
判断一颗树是否是另一棵树的子树还是会用到两棵树是否相等。只不过这道题目需要注意一下开始比较的条件。我们先写一个框架
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(rootNULL){return false;}if(root-valsubRoot-val){//开始比较……}return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);//遍历左子树 // 遍历右子树
} 如果完整的树为NULL那就不在需要判断了直接返回false。然后开始比较root的值是否与subRoot的值相等如果相等就从值相等的节点位置开始判断两棵树是否相同。在寻找相同值的过程中我们需要遍历二叉树遍历二叉树最简便的方法就是使用递归只要root左子树或右子树有一个存在子树相同那就返回true所以这里使用 “ || ” 。
注意只有返回类型为bool类型时才可以进行或||的操作
完整代码如下
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(rootNULL){return false;}if(root-valsubRoot-val){if(isSameTree(root,subRoot)) //isSameTree函数使用的是上述题目2的代码{return true;}}return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
} 题目5二叉树的前序遍历 题目描述 题目链接
二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/
✨题目解析 这道二叉树的前序遍历和我们·之前的不太一样我们需要把遍历的值放在一个数组中所以首先我们还需要知道二叉树的节点个数才可以创建数组然后再开始遍历二叉树。 我们可以分两个接口来写
int* preorderTraversal(struct TreeNode* root, int* returnSize){*returnSize0; //返回的数组大小int nTreeSize(root);int* ret(int*)malloc(sizeof(int)*n);preorder(root,ret,returnSize);//遍历二叉树return ret;//返回数组
}
这里的前序遍历和之前没什么区别区别就在原本输出的位置需要把数据存到数组中
void preorder(struct TreeNode* root,int* arr,int* i)
{if(rootNULL){return;}//前序遍历的顺序根、左子树、右子树arr[(*i)]root-val;preorder(root-left,arr,i); preorder(root-right,arr,i);
}
完整代码如下
int TreeSize(struct TreeNode* root)
{if(rootNULL){return 0;}return TreeSize(root-left)TreeSize(root-right)1;
}
void preorder(struct TreeNode* root,int* arr,int* i)
{if(rootNULL){return;}arr[(*i)]root-val;preorder(root-left,arr,i); preorder(root-right,arr,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){*returnSize0;int nTreeSize(root);int* ret(int*)malloc(sizeof(int)*n);preorder(root,ret,returnSize);return ret;
} 此外还有中序遍历、后序遍历、大家可以自行练习。
二叉树的中序遍历
二叉树的后序遍历 总结 本期主要的内容是学会二叉树的递归遍历除此之外二叉树还有层序遍历层序遍历需要的数据结构更复杂一点下期我再向大家一一介绍以上便是本前期全部内容最后感谢阅读
