LeetCode刷题day06（二叉树递归套路）

二叉树的递归套路就是，二叉树的左子树和右子树给结点某些信息，这个结点利用这些信息让整棵树满足题目要求。

1.题目1：将二叉树转换成双向链表

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XyGH3Wae-1652774617912)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1652751128779.png)]$

【思路】二叉树递归套路。每个结点的左右子树分别给这个结点已经链接好的双向链表结构的头和尾结点，然后和这个结点双向链接即可。

【代码】

//搜索二叉树转换成双向链表后，头和尾返回
class Info {
    public:
    Info(Node* start, Node* end) : start(start), end(end) {}
    Node* start = nullptr;
    Node* end = nullptr;
};
//以x为头的整棵搜索二叉树，用有序双向链表方式，连好并且返回，整个有序双向链表的
//头节点和尾结点
Info* process(Node* x) {
    if (x == nullptr) {
        return new Info(nullptr, nullptr);
    }
    Info* leftHeadEnd = process(x->left);
    Info* rightHeadEnd = process(x->right);
    if (leftHeadEnd->end != nullptr) {
        leftHeadEnd->end->right = x;
    }
    x->left = leftHeadEnd->end;
    x->right = rightHeadEnd->start;
    if (rightHeadEnd->start != nullptr) {
        rightHeadEnd->start->left = x;
    }
    return  new Info(leftHeadEnd->start != nullptr ? leftHeadEnd->start : x, rightHeadEnd->end != nullptr ? rightHeadEnd->end : x);
}

2.题目2：返回最大二叉搜索子树结点个数

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-riREEf9y-1652774617913)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1652753020951.png)]$

【思路】二叉搜索树递归套路。每个结点的左右子树返回左右子树最大二叉搜索子树的的最大结点个数。

【代码】

//返回类型
class Info {
public:
    Info() = default;
    Info(bool is, int minV, int maxV, int size) : 
    	isBst(is), minVal(minV), 
    	maxVal(maxV), maxBstSize(size) {}
    bool isBst = true; //子树是否是二叉搜索树
    int minVal = INT32_MAX; //最大搜索子树最小值
    int maxVal = INT32_MIN; //最大搜索子数最大值
    int maxBstSize = 0; //最大搜索子树结点个数
};
Info* process(Node *root) {
    if (root == nullptr) {
        return nullptr;
    }
    Info* leftInfo = process(root->left);
    Info* rightInfo = process(root->right);
    //初始化当前节点返回值
    bool isBst = true;
    int minVal = root->val;
    int maxVal = root->val;
    int maxBstSize = 1;
    //1.情况1：左右子树都为空
    if (!leftInfo && !rightInfo) {
        return new Info(isBst, minVal, maxVal, maxBstSize);
    }
    //2.情况2：左右子树不全为空，且子树本身不是二叉搜索树
    if (leftInfo && !rightInfo->isBst || 
        rightInfo && !leftInfo->isBst ||
       	!leftInfo->isBst && !rightInfo->isBst) {
        int leftSize = leftInfo == nullptr ? 0 : leftInfo->maxBstSize;
        int rightSize = rightInfo == nullptr ? 0 : rightInfo->maxBstSize;
        maxBstSize = max(leftSize, rightSize);
        return new Info(false, minVal, maxVal, maxBstSize);
    }
    //3.情况3：整棵树是二叉搜索树
    if (!leftInfo && rightInfo->isBst ||
        !rightInfo && leftInfo->isBst ||
       leftInfo->isBst && rightInfo->isBst) {
        int leftVal = leftInfo == nullptr ? INT32_MIN : leftInfo->maxVal;
        int rightVal = rightInfo == nullptr ? INT32_MAX : rightInfo->minVal;
        if (leftVal < root->val && root->val < rightVal) {
            minVal = leftInfo == nullptr ? root->val : leftInfo->minVal;
            maxVal = rightInfo == nullptr ? root->val : rightInfo->maxVal;
            int leftSize = (leftInfo == nullptr ? 0 : leftInfo->maxBstSize);
            int rightSize = (rightInfo == nullptr ? 0 :rightInfo->maxBstSize);
            maxBstSize = 1 + leftSize + rightSize;
            return new Info(true, minVal, maxVal, maxBstSize);
        } else {
            int leftSize = leftInfo == nullptr ? 0 : leftInfo->maxBstSize;
            int rightSize = rightInfo == nullptr ? 0 : rightInfo->maxBstSize;
            maxBstSize = max(leftSize, rightSize);
            return new Info(false, minVal, maxVal, maxBstSize);
        }
    }
}

3.题目3：二叉树的深度

剑指 Offer 55 - I. 二叉树的深度

难度简单187

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

【思路】上题太复杂，来一个简单的二叉树递归套路。左树右子树分别给了左右子树最大深度的信息，这个结点的最大深度就是左右深度中大的那个加1。

【代码】

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return 1 + max(leftDepth, rightDepth);
}