- 前言
- LeetCode104.二叉树的最大深度
- 解题思路
- 图示
- 代码
- LeetCode98.验证二叉搜索树
- 二叉搜索树
- 解题思路
- 图示
- 代码
- LeetCode101.对称二叉树
- 解题思路
- 图示
- 代码
- 微信公众号文章
深度优先搜索递归实现解决三个题
①确定递归退出条件
②确定传递的参数
点击链接开始刷题φ(゜▽゜*)♪：LeetCode104.二叉树的最大深度
解题思路传入二叉树的根节点,该二叉树的最大深度为左子树的最大深度加上右子树的最大深度
左子树和右子树也同样拥有自己的左右子树
那么就用递归解决
每次将root的左右子树的根节点传递过去,返回该结点左右子树中的最大深度+1
当root为NULL时退出,开始向上返回
代码
class Solution {
public:
int maxDepth(TreeNode* root) {
//退出条件
if(root==NULL){
return 0;
}
//将root的左右子树的根节点传递过去,返回该结点左右子树中的最大深度+1
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(height),height为二叉树的高度
点击链接开始刷题φ(゜▽゜*)♪：LeetCode98.验证二叉搜索树
二叉搜索树- 结点的左子树只包含小于当前结点的树
- 结点的右子树只包含大于当前结点的树
- 所有左子树和右子树自身必须也是二叉搜索树
递归判断
- 当前结点的左孩子的值是否小于当前结点的值，是则返回true，不是则返回false
- 当前结点的右孩子的值是否大于当前结点的值，是则返回true，不是则返回false
- 但是按照这个思路将会发现类似这样的错误
所以我们要增加一个区间限制
让当前结点左子树的所有结点的值均小于当前结点的值
让当前结点右子树的所有结点的值均大于当前结点的值
我们利用另一个函数来辅助实现，该函数可以判断当前结点的值是否在区间内
- 对于传入的当前结点，一定要处于传入的(最小结点的值，最大结点的值)这个区间内，这个区间传递下去是会一直更新的
- 将当前结点的左孩子传递下去时，一并传入当前结点(作为下一层递归的最大结点)和最小结点(依旧作为下一层递归的最小节点)
- 将当前结点的右孩子传递下去时，一并传入最大结点(依旧作为下一层递归的最大结点)和当前结点(作为下一层递归的最小结点)
代码
class Solution {
public:
bool isValidBST(TreeNode* root) {
return help(root,NULL,NULL);
}
bool help(TreeNode* root,TreeNode* treemax,TreeNode* treemin){
if(root==NULL)
return true;
if(treemax!=NULL&&root->val>=treemax->val)
return false;
if(treemin!=NULL&&root->val<=treemin->val)
return false;
return help(root->left,root,treemin)&&help(root->right,treemax,root);
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(n)
点击链接开始刷题φ(゜▽゜*)♪：LeetCode101.对称二叉树
解题思路递归判断二叉树是否对称
从根节点的第一层子节点开始，判断 根节点的左子节点 是否等于 根节点的右子节点
即判断 root->left 是否等于 root->right
利用一个辅助函数来实现递归
- 若传入的左右两个节点都为空，那么这两个空节点的父节点为叶子节点，返回 true
- 若传入的左右两个节点只有一个为空，或者两个节点的值不一样，返回 false
- 下一层递归就是传入 (左子节点的左子节点,右子节点的右子节点) 和
(左子节点的右子节点,右子节点的左子节点) 进行下一轮的判断
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root==NULL)
return true;
return help(root->left,root->right); //从根节点的第一层子节点开始
}
bool help(TreeNode* left,TreeNode* right){
if(left==NULL&&right==NULL)
return true; //若传入的左右两个节点都为空，那么这两个空节点的父节点为叶子节点，返回true
if(right==NULL||left==NULL||left->val!=right->val)
return false; //若传入的左右两个节点只有一个为空，或者两个节点的值不一样，返回false
return help(left->left,right->right)&&help(left->right,right->left); //进入下一层递归
//左子节点的左子节点和右子节点的右子节点进行比较;左子节点的右子节点和右子节点的左子节点进行比较
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
LeetCode104.二叉树的最大深度&98.验证二叉搜索树&101.对称二叉树
