[数据结构与算法]LeetCode104.二叉树的最大深度&98.验证二叉搜索树&101.对称二叉树（C++）

前言

深度优先搜索递归实现解决三个题
①确定递归退出条件
②确定传递的参数

LeetCode104.二叉树的最大深度

点击链接开始刷题φ(゜▽゜*)?：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.验证二叉搜索树

点击链接开始刷题φ(゜▽゜*)?：LeetCode98.验证二叉搜索树

二叉搜索树

1. 结点的左子树只包含小于当前结点的树
2. 结点的右子树只包含大于当前结点的树
3. 所有左子树和右子树自身必须也是二叉搜索树

解题思路

递归判断

1. 当前结点的左孩子的值是否小于当前结点的值，是则返回true，不是则返回false
2. 当前结点的右孩子的值是否大于当前结点的值，是则返回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.对称二叉树

点击链接开始刷题φ(゜▽゜*)?：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.对称二叉树