LeetCode 91~110题解-EW帮帮网

LeetCode91.解码方法：

题目描述：

一条包含字母 A-Z 的消息通过以下映射进行了编码：

“1” -> ‘A’

“2” -> ‘B’

…

“25” -> ‘Y’

“26” -> ‘Z’

然而，在解码已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（“2” 和 “5” 与 “25”）。

例如，“11106” 可以映射为：

“AAJF” ，将消息分组为 (1, 1, 10, 6)
“KJF” ，将消息分组为 (11, 10, 6)
消息不能分组为 (1, 11, 06) ，因为 “06” 不是一个合法编码（只有 “6” 是合法的）。
注意，可能存在无法解码的字符串。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。如果没有合法的方式解码整个字符串，返回 0。

题目数据保证答案肯定是一个 32 位的整数。

示例 1：

输入：s = “12”
输出：2
解释：它可以解码为 “AB”（1 2）或者 “L”（12）。

示例 2：

输入：s = “226”
输出：3
解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

示例 3：

输入：s = “06”
输出：0
解释：“06” 无法映射到 “F” ，因为存在前导零（“6” 和 “06” 并不等价）。

提示：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

思路：

我们可以对于给出的数字字符串将它一位一位往后面看，比如当前在第i位，那么它与前面的数字字符组成的可编码的方案有：
1.如果当前数字字符能独自编码出来（也就是范围在1~9） 2.它与前面数字的组合能够形成二位数字的编码（范围在10~26）
那么我们可以看出当前字符加上之前的字符的方案数可以由之前的方案确定，那么可以使用动态规划思想：设定集合f[i]表示以i字符结尾中的可以编码出来的方案数
微信截图_20241127182203.png

微信截图_20241127183449.png

时间复杂度：O(n)

注释代码：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<int> f(n + 1);  //表示s的前i个字符中有多少种编码方案
        f[0] = 1; //一个字符没有也是一种方案
        for(int i = 1; i <= n; i++) //从第一个字符开始
        {
            if(s[i] >= '1' && s[i] <= '9') f[i] += f[i - 1]; //当前位独自编码
            if(i > 1) //如果前面有多于两位，那么可以组成10~26了
            {
                int t = (s[i - 1] - '0') * 10 + s[i] - '0';
                 //看与前面位是否可以组成编码数字范围
                cout<<t<<endl;
                if(t >= 10 && t <= 26) f[i] += f[i - 2]; //可以的话加上i-2位的方案数
            }
        }
        return f[n];
    }
};

纯享版：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<int> f(n + 1);
        f[0] = 1;
        for(int i = 1; i <= n; i++)
        {
            if(s[i] >= '1' && s[i] <= '9') f[i] += f[i -1];
            if(i > 1)
            {
                int t = (s[i - 1] - '0') * 10 + s[i] - '0';
                if(t >= 10 && t <= 26)
                {
                    f[i] += f[i - 2];
                }
            }
        }
        return f[n];
    }
};

LeetCode92.反转链表Ⅱ：

题目描述：

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

示例 1：
微信截图_20241127192531.png

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶：你可以使用一趟扫描完成反转吗？

思路：

写链表题最重要的就是画图，将题目意思以图形化的方式展示一遍，大概就能知道怎么做了，这里只要将m ~ n节点之间的边如反转链表Ⅰ中一样依次翻转一次，然后将头尾分别连接起来即可：
微信截图_20241127184212.png

时间复杂度：O(n)

注释代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        auto a = dummy;
        for(int i = 0; i < m - 1; i++) a = a -> next; //找到第m个节点的前一个节点：a
        auto b = a -> next, c = b -> next; //b， c翻转两个相邻节点之间的连接
        for(int i = 0; i < n - m; i++) //m ~ n ：n -m + 1个节点，n - m条边
        {
            auto t = c -> next; 
            c -> next = b;
            b = c, c = t;
        }
        a -> next -> next = c;  //第m个节点指向c
        a -> next = b; //a指向第n个节点
        return dummy -> next; 
    }
};

纯享版：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        auto a = dummy;
        for(int i = 0; i < m - 1; i++) a = a -> next;
        auto b = a -> next, c = b -> next;
        for(int i = 0; i < n - m; i++)
        {
            auto t = c -> next;
            c -> next = b;
            b = c, c = t;
        }
        a -> next -> next = c;
        a -> next = b;
        return dummy -> next; 
    }
};

LeetCode93.复原IP地址：

题目描述：

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例 1：

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

示例 2：

输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：

输入：s = “101023”
输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

提示：

1 <= s.length <= 20
s 仅由数字组成

思路：

这种题还是有点类似于排列组合问题，也就是给出一串数字字符串，让你找到符合IP网址要求的组合数：所以我们需要设定四个参数： s：字符串本身， u：当前找到第几个数了， k :当前是IP网址的第几个空， path：填的数是什么
微信截图_20241127200753.png
微信截图_20241127194428.png

时间复杂度：

相当于给出n个字符，在这些字符的中间插入’.‘，也就是在n-1个间隔中插入3个’.'，每个字符对应不同情况，所以时间复杂度为:
微信截图_20241127201219.png

注释代码：

class Solution {
public:
    vector<string> res;
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0, "");
        return res;
    }
    void dfs(string& s, int u, int k, string path)
    {
        if(u == s.size())
        {
            if(k == 4)  //凑齐四位的话
            {
                path.pop_back(); //将最后一个点去除
                res.push_back(path);
                return;
            }
        }
        if(k == 4) return;  //剪枝，如果此时已经到达IP地址的四位还没结束的话直接返回

        for(int i = u, t = 0; i < s.size(); i++) //从当前第u位开始，t记录当前位网址的值
        {
            if(i > u && s[u] == '0') break; //有前导0，直接退出
            t = t * 10 + s[i] - '0';
            if(t <= 255)  //如果满足IP网址要求
            {
                //递归到下一层，从当前第i + 1个开始，寻找到网址的第k+ 1位
                dfs(s, i + 1, k + 1, path + to_string(t) + '.');

            }else break; //如果不在0 ~ 255范围说明不属于网址
        }
    }
};

纯享版：

class Solution {
public:
    vector<string> res;
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0, "");
        return res;
    }
    void dfs(string& s, int u, int k, string path)
    {
        if(u == s.size())
        {
            if(k == 4)
            {
                path.pop_back();
                res.push_back(path);
                return;
            }
        }
        if(k >= 4) return;

        for(int i = u, t = 0; i < s.size(); i++)
        {
            if(i > u && s[u] == '0') break;
            t = t * 10 + s[i] - '0';
            if(t <= 255)
            {
                dfs(s, i + 1, k + 1, path + to_string(t) + '.');
            }else break;
        }
    }
};

LeetCode94.二叉树的中序遍历：

题目描述：

给定一个二叉树的根节点 root ，返回它的中序遍历。

示例 1：
微信截图_20241128185308.png

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路：

算法1：递归做法

时间复杂度：O(n)

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root)
    {
        if(!root) return;
        dfs(root -> left);
        res.push_back(root -> val);
        dfs(root -> right);
    }
};

纯享版：

算法2: 迭代做法：

思路：二叉搜索树一般迭代搜索方式：

微信图片编辑_20241128192315.jpg

时间复杂度：O(n)

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size())
        {
            while(root)
            {
                stk.push(root); //将左边节点加入栈中
                root = root -> left;  //同时继续往左边搜索
            }
            root = stk.top(); //拿到栈顶的节点
            stk.pop();
            res.push_back(root -> val);  //将栈顶节点值放入答案集合
            root = root -> right; //搜索右节点
        }
        return res;
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size())
        {
            while(root)
            {
                stk.push(root);
                root = root -> left;
            }

            root = stk.top();
            stk.pop();
            res.push_back(root -> val);
            root = root -> right;
        }
        return res;
    }
};

2024/12/24二刷：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        while(root || stk.size())
        {
            while(root)
            {
                stk.push(root);
                root = root -> left;
            }

            root = stk.top();
            stk.pop();
            res.push_back(root -> val);
            root = root -> right;
        }
        return res;
    }
    
};

2025/1/7:

迭代做法都不记得了，差劲！！

 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
    void dfs(TreeNode* root)
    {
        if(!root) return;
        dfs(root -> left);
        res.push_back(root -> val);
        dfs(root -> right);
    }
};

递归做法：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        while(root || stk.size())
        {
            while(root)
            {
                stk.push(root);
                root = root -> left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root -> val);
            root = root -> right;
        }
        return res;
    }
};

LeetCode95.不同的二叉搜索树Ⅱ：

题目描述：

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树。可以按任意顺序返回答案。

示例 1：

微信截图_20241128202554.png
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 8

思路：

对于一棵二叉搜索树来说，一个重要的性质就是它的中序遍历为升序，中序遍历的过程为左 -> 根 -> 右，在一段连续的区间中，左子树的节点值肯定小于右子树的节点值，那么我们可以枚举区间中的每一个点作为根节点，然后通过根节点将区间一分为二，左边是组成左子树的方案，右边是组成右子树的方案，如果给每个结点标记上编号，意思就是说所有左子树节点的编号一定小于根节点，所有右子树的结点编号大于根节点。在此题中给定了一个中序遍历顺序1 ~ n，于是我们的思路如下：

微信截图_20241128200319.png

·先枚举根节点的位置，将问题划分为分别递归求解左边子树和右边子树
·递归返回的是所有合法方案的集合，所以枚举每种合法的左右儿子
·枚举左右儿子和根节点作为一种合法方案记录下来

###对于每个位置上的根节点来说，左子树的任何一种方案加上右子树的任何一种方案都能组成一种方案

时间复杂度：

微信截图_20241128204545.png

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(!n) return {};
        return dfs(1, n);
    }
    vector<TreeNode*> dfs(int l, int r)
    {
        if(r < l) return {NULL}; //所有子树是连续的一段
        vector<TreeNode*> res;

        for(int i = l; i <= r; i++)
        {
            auto left = dfs(l, i - 1); //以当前节点为根的左子树合法方案
            auto right = dfs(i + 1, r); //以当前节点为根的右子树合法方案
            for(auto l : left) //取一个左子树
            {
                for(auto r : right)  //取一个右子树
                {
                    auto root = new TreeNode(i); 
                    root -> left = l, root -> right = r;  //给当前根节点添加左右子树
                    res.push_back(root);  //返回以当前节点为根节点的一种方案
                }
            }
        }
        return res;
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(!n) return {};
        return dfs(1, n);
    }
    vector<TreeNode*>dfs(int l, int r)
    {
        if(l > r) return {NULL};
        vector<TreeNode*> res;

        for(int i = l; i <= r; i++)
        {
            auto left = dfs(l, i -1);
            auto right = dfs(i + 1, r);
            for(auto l : left)
            {
                for(auto r : right)
                {
                    auto root = new TreeNode(i);
                    res.push_back(root);
                    root -> left = l;
                    root -> right = r;
                }
            }
        }
        return res;
    }
};

LeetCode96.不同的二叉搜索树：

题目描述：

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

示例 1：
微信截图_20241128202554.png

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

思路：

有了上一题的基础，我们很清楚得知，每个位置作为节点的方案数由左子树和右子树的方案数相乘得到，
##结论：同时可以发现在长度相同的区间中方案数相同，例如： 1~n 和2~n+1的二叉搜索树方案数其实是相同的，将1~n的1节点映射到2~n+1的2节点…以此类推，可以将每个节点都映射到对应的位置上，于是知道连续区间长度相同的二叉搜索树方案是一样的
##这里使用动态规划思想：设定集合f[i]表示1_{i中的方案数，j表示1}i上的任意一个数由上面可知f[1~i]= f[1~j-1]*f[j+1 ~ i],但是由于上述结论可知只要区间长度一致，方案数一致，那么f[j+1~i ] = f[i - (j + 1) + 1] = f[i-j]
微信截图_20241128202002.png

时间复杂度：O(n * n)

注释代码：

class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n + 1);
        f[0] = 1;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                f[i] += f[j - 1] *  f[i - j];
            }
        }
        return f[n];
    }
};

纯享版：

class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n + 1);
        f[0] = 1;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                f[i] += f[j - 1] * f[i - j];
            }
        }
        return f[n];
    }
};

LeetCode97.交错字符串：

题目描述：

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空
子字符串
：

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
输出：true

示例 2：

输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
输出：false

示例 3：

输入：s1 = “”, s2 = “”, s3 = “”
输出：true

提示：

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成

进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?

思路：

遇到字符串匹配问题最多的就是利用动态规划来解决，因为字符串匹配是一类一类的进行区分，比如这里的s1和s2是否能匹配上s3，我们设定集合f[i,j]表示：所有s1的[1 ~ i]个字符和s2的[1 ~ j]交错组成s3的[1 ~ i + j]的方案集合，属性就是判断集合是否为空，不为空说明可以交错组合成功，否则不能。

借此将集合划分为两类：
1.s3的第i+ j个字符是由s1的最后一个字符，也就是s1[i]组成的：那么f[i][j] = f[i - 1][j]
2.s3的第i+j个字符是由s2的最后一个字符，也就是s2[j]组成的，那么f[i][j] = f[i][j] || f[i][j - 1]，这里要或上f[i][j]是为了防止同时匹配的情况发生，如果s1[i] == s1[j] == s[i + j]那么只需要一种发生即可满足

微信图片编辑_20241129190915.jpg

时间复杂度：O(n * n)

微信截图_20241129191846.png

注释代码：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(), m = s2.size();
        if(s3.size() != n + m) return false; //长度不符合就不可能匹配的上
        vector<vector<int>> f(n + 1, vector<int>(m + 1));  //数组长度多加一位
        s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;//都从1开始比较好处理
        for(int i = 0; i <= n; i++)
        {
            for(int j = 0; j <= m; j++) //从0开始是因为
            {
                if(!i && !j) f[i][j] = true;  //如果两个都是空串那么空串肯定可以匹配空串
                else{
                    if(i && s1[i] == s3[i + j]) f[i][j] = f[i - 1][j]; //s3的最后一个字符是由s2匹配的，那么s1的前i-1个和s2的前j个肯定要先能匹配上
                    if(j && s2[j] == s3[i + j]) f[i][j] = f[i][j] || f[i][j - 1];
                }
            }
        }
        return f[n][m];
    }
};

纯享版：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(), m = s2.size();
        if(s3.size() != n + m) return false;
        s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;
        vector<vector<bool>> f(n + 1, vector<bool> (m + 1));
        for(int i = 0; i <= n; i++)
        {
            for(int j = 0; j <= m; j++)
            {
                if(!i && !j) f[i][j] = true;
                else{
                    if(i && s1[i] == s3[i + j]) f[i][j] = f[i - 1][j];
                    if(j && s2[j] == s3[i + j]) f[i][j] = f[i][j] || f[i][j - 1];
                }
            }
        }
        return f[n][m];
    }
};

LeetCode98.验证二叉搜索树：

题目描述：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左
子树
只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

微信截图_20241129200142.png
输入：root = [2,1,3]
输出：true

示例 2：
微信截图_20241129200148.png

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

思路：

时间复杂度：

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        return dfs(root)[0];
    }
    vector<int> dfs(TreeNode* root)
    {
        //返回三个信息： 1.0/1： 当前子树合不合格：合格：1 不合格： 0
        //2，3. 当前子树中的最小值和最大值
        vector<int> res{1, root -> val, root -> val};
        //验证左子树
        if(root -> left)
        {
            auto t = dfs(root -> left); //先递归处理当前左子树
            //拿到当前左子树的情况，如果是有问题的或者是当前左子树的最大值大于父节点值，说明不是合格的二叉搜索树
            if(!t[0] || t[2] >= root -> val) res[0] = 0; 
            res[1] = min(res[1], t[1]);  //res[1]记录子树中的最小值
            res[2] = max(res[2], t[2]); //res[2]记录子树中的最大值
        }
        //验证右子树
        if(root -> right)
        {
            auto t = dfs(root -> right);
            if(!t[0] || t[1] <= root -> val) res[0] = 0;
            res[1] = min(res[1], t[1]);
            res[2] = max(res[2], t[2]);
        }
        return res;
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        return dfs(root)[0];

    }

    vector<int> dfs(TreeNode* root)
    {
        vector<int> res{1, root -> val, root -> val};
        if(root -> left)
        {

            auto t = dfs(root -> left);
            if(!t[0] || t[2] >= root -> val) res[0] = 0;
            res[1] = min(res[1], t[1]);
            res[2] = max(res[2], t[2]);
        }

        if(root -> right)
        {
            auto t = dfs(root -> right);
            if(!t[0] || t[1] <= root -> val) res[0] = 0;
            res[1] = min(res[1], t[1]);
            res[2] = max(res[2], t[2]);
        }
        return res;
    }
};

LeetCode99.恢复二叉树：

题目描述：

给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树。

示例 1：
微信截图_20241129234256.png

微信截图_20241130181746.png

微信截图_20241130181753.png

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：
微信截图_20241129234302.png

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

树上节点的数目在范围 [2, 1000] 内
-2^31 <= Node.val <= 2^31 - 1

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

思路：

微信截图_20241130181735.png

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = NULL, *second, *last = NULL;
        while(root)
        {
            if(!root -> left) //如果不存在左儿子
            {
                if(last && last -> val > root -> val) //如果上一节点存在并且出现逆序对
                {
                    if(!first) first = last ,second = root; //判断是否为第一对逆序对
                    else second = root; //如果不是，只需记录第二对逆序对的第二个节点
                }
                last = root;
                root = root -> right;
            }else{  //存在左儿子
                auto p = root -> left;
                while(p -> right && p -> right != root) p = p -> right; //找到前驱节点
                if(!p -> right) //如果前驱节点的右儿子是空的，使用前驱节点的右儿子记录当前父节点
                {
                    p -> right = root;
                    root = root -> left; //进入左子树进行遍历
                }else{
                    //已经指向父节点，重新清零，并从当前父节点开始遍历
                    p -> right = NULL; 
                    if(last && last -> val > root -> val)
                    {
                        if(!first) first = last, second = root;
                        else second = root;
                    }
                    last = root; //将当前点更新成上一个点
                    root = root -> right; //走向右儿子
                }
                
            }
        }
        swap(first -> val, second -> val);
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = NULL, *second, *last = NULL;
        while(root)
        {
            if(!root -> left)
            {
                if(last && last -> val > root -> val) 
                {
                    if(!first) first = last, second = root;
                    else second = root;
                }
                last = root;
                root = root -> right;
            }else{
                auto p = root -> left;
                while(p -> right && p -> right != root) p = p -> right;
                if(!p -> right)
                {
                    p -> right = root;
                    root = root -> left;
                }else{
                    p -> right = NULL;
                    if(last && last -> val > root -> val) 
                    {
                        if(!first) first = last, second = root;
                        else second = root;
                    }
                    last = root;
                    root = root -> right;
                }
                
            }
        }
        swap(first -> val, second -> val);
    }
};

LeetCode100.相同的树：

题目描述：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：
微信截图_20241130182524.png

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：
微信截图_20241130182531.png

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

微信截图_20241130182539.png
输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

思路：

对于两棵树，要验证他们是否相同，就是对两棵树同步进行遍历验证，验证每一个节点是否存在，存在的话是否值相同，同步遍历左子树和右子树

时间复杂度：O(n)

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!q && !p) return true;  //两棵树当前节点都为空那么返回true
        if(!q || !p || p -> val != q -> val) return false; //如果其中一颗树为空或者两棵树当前节点值不一样，则返回false
        return isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right)  //分别递归遍历两棵树的左子树和右子树
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;
        if(!p || !q || p -> val != q -> val) return false;
        return isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right);
    }
};

LeetCode101.对称二叉树：

题目描述：

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

微信截图_20241130184857.png
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
微信截图_20241130184904.png

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

思路：

与 LeetCode100.相同的树一样的做法，这里是要同步去比较当前节点下的左子树和右子树是否对称：
微信截图_20241130184109.png

时间复杂度：O(n)

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root -> left, root -> right);
    }
    bool dfs(TreeNode *l, TreeNode *r)
    {
        if(!l && !r) return true;  //左右子树均为空，则为true
        if(!l || !r || l -> val != r -> val) return false; //有一侧为空或者二者的值不一样则为false
        //递归验证左节点的左子树和右节点的右子树，以及左节点的右子树和右节点的左子树是否一致
        return dfs(l -> left, r -> right) && dfs(l -> right, r -> left); 
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root -> left, root -> right);
    }
    bool dfs(TreeNode* l, TreeNode* r)
    {
        if(!l && !r) return true;
        if(!l || !r || l -> val != r -> val) return false;
        return dfs(l -> left, r -> right) && dfs(l -> right, r -> left);
    }
};

LeetCode102.二叉树的层序遍历：

题目描述：

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

示例 1：
微信截图_20241130194809.png

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

思路：

树的遍历是常考察的算法：一般数的遍历有：前中后序遍历，以及层序遍历，这里的层序遍历使用宽搜的思想，用队列维护每一层的节点
微信截图_20241130194920.png

时间复杂度：

微信截图_20241130200835.png

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(q.size())
        {
            vector<int> level; //存该层的所有节点
            auto len = q.size();  //队列当前元素长度
            while(len--)
            {
                auto t = q.front();  //取出队头
                q.pop();
                //将当前节点放入当前层的集合中
                level.push_back(t -> val);
                //将当前层的下一层节点放入队列
                if(t -> left) q.push(t -> left);
                if(t -> right) q.push(t -> right);

            }
            res.push_back(level); //将该层所有节点记录下来

        }
        return res;
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(q.size())
        {
            vector<int> level;
            auto len = q.size();
            while(len--)
            {   
                auto t = q.front();
                q.pop();
                level.push_back(t -> val);
                if(t -> left) q.push(t -> left);
                if(t -> right) q.push(t -> right);
                
            }
            res.push_back(level);
        }
        return res;
    }
};

2024/12/27二刷：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> res;
        if(!root) return res;
        q.push(root);
        while(q.size())
        {
            int len = q.size();
            vector<int> level;
            while(len--)
            {
                auto root = q.front();
                level.push_back(root -> val);
                q.pop();
                if(root -> left) q.push(root -> left);
                if(root -> right) q.push(root -> right);
            }
            res.push_back(level);
        }
        return res;
    }
};

LeetCode103.二叉树的锯齿形层次遍历：

题目描述：

给你二叉树的根节点 root ，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

微信截图_20241201183419.png
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

思路：

根据上题的思路对每一层的层数奇偶进行判断，对偶数层数进行翻转

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root) q.push(root);
        int n = 1;
        while(q.size())
        {
            n++;
            vector<int> level;
            int len = q.size();
            while(len--)
            {
                auto t = q.front();
                q.pop();
                level.push_back(t -> val);
                if(t -> left) q.push(t -> left);
                if(t -> right) q.push(t -> right);
            }
            if(n % 2 != 0) reverse(level.begin(), level.end()); 
            res.push_back(level);
        }
        return res;
    }
};

纯享版：

LeetCode104.二叉树的最大深度：

题目描述：

给定一个二叉树 root ，返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

微信截图_20241201185345.png

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

树中节点的数量在 [0, 10^4] 区间内。
-100 <= Node.val <= 100

思路：

这题可以继续使用上题的层序遍历也可以使用dfs，bfs，但是这里也可以反过来，递归找当前节点下的左右子节点到最底层节点的步数，求左右子节点带最底层节点的深度最大值+1便是当前节点到最底层节点的深度

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return max(maxDepth(root -> left), maxDepth(root -> right)) + 1;
    }
};

LeetCode105.从前序与中序遍历序列构造二叉树：

题目描述：

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:
微信截图_20241201183419.png

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

思路：

本题的重心在于知道前序遍历的第一个点必定是当前根节点，于是可以根据根节点的值找到它在中序遍历中的位置，又根据中序遍历的性质：中序遍历的同一颗子树是连续的一段，也就是找到根节点之后，根节点左边区间段的就是当前根节点下的左子树，右边区间段就是当前根节点下的右子树：每次通过当前节点延展找到当前节点下的左节点和右节点，以此递归下去最终延展出整颗树（前提是不能有重复元素）
微信截图_20241201203312.png
微信截图_20241201201722.png

微信截图_20241201201905.png

时间复杂度：

微信截图_20241201203304.png

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i;  //将中序遍历中的节点作一个哈希映射
        return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* build(vector<int>& pre, vector<int>& in, int pl, int pr, int il, int ir)
    {
        if(pl > pr) return NULL; //如果左端点比右端点大，说明已经找不到节点了
        auto root = new TreeNode(pre[pl]); //定义当前根节点
        int k = pos[root -> val];  //根据当前根节点的哈希映射找到根节点对应的在中序遍历中的下标
        root -> left = build(pre, in, pl + 1, pl + 1 + k - 1 - il, il, k - 1); //找到当前节点的左节点
        root -> right = build(pre, in, pl + 1 + k - 1 - il + 1, pr, k + 1, ir); //找到右节点
        return root; //返回当前节点
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        for(int i = 0; i < n; i++) pos[inorder[i]] = i;
        return build(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    TreeNode* build(vector<int>& pre, vector<int>& in, int pl, int pr, int il, int ir)
    {
        if(pl > pr) return NULL;
        auto root = new TreeNode(pre[pl]);
        int k = pos[root -> val];
        root -> left = build(pre, in, pl + 1, pl + 1 + k - 1 - il, il, k - 1);
        root -> right = build(pre, in, pl + 1 + k - 1 - il + 1, pr, k + 1, ir);
        return root;
    }
};

LeetCode106.从中序与后序遍历序列构造二叉树：

题目描述：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

示例 1:
微信截图_20241201183419.png

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由不同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

思路：

与上题思路一致：
微信截图_20241202200526.png
具体步骤如下：
1.首先利用后序遍历找根节点，后序遍历的最后一个节点就是根节点的值
2.根据根节点的值找到根节点在中序遍历中的位置K，由中序遍历的性质：根节点K左边是当前根节点中序遍历下的左子树，右边则是当前根节点中序遍历下的右子树
3.假设前面的中序遍历中左子树的长度是l，那么在后序遍历中前l个节点就是左子树对应的节点的后序遍历，剩下的则是对应中序遍历右边段的右子树节点的后序遍历
4.有了左右子树的后序遍历和中序遍历，我们可以先递归创建出左右子树，然后创建根节点

时间复杂度：在哈希表中记录中序遍历中每个元素对应的值时间消耗是O(1)的，然后查询也是O(1)的，创建每个节点需要的时间是O(1)的，所以总的时间复杂度是O(n)的

注释代码：

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> pos;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for(int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i;
        return build(postorder, inorder, 0, postorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* build(vector<int>& postorder, vector<int>& inorder, int pl, int pr, int il, int ir)
    {
        if(pl > pr) return NULL;
        auto root = new TreeNode(postorder[pr]);
        int k = pos[root -> val];
        root -> left = build(postorder, inorder, pl, pl + k - 1 - il, il, k - 1);
        root -> right = build(postorder, inorder, pl + k - 1 - il + 1, pr - 1, k + 1, ir);
        return root;
    }
};

LeetCode107.二叉树的层次遍历Ⅱ：

题目描述：

给你二叉树的根节点 root ，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：
微信截图_20241201183419.png

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

思路：

只要将从上往下的层次遍历最终的答案翻转一下即可

时间复杂度：

每个节点只会进队列一次出队列一次，时间复杂度是O(n) 的

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(q.size())
        {
            vector<int> level;
            int len = q.size();
            while(len--)
            {
                auto t = q.front();
                q.pop();
                level.push_back(t -> val);
                if(t -> left) q.push(t -> left);
                if(t -> right) q.push(t -> right);
            }
            res.push_back(level);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

纯享版：

LeetCode108.将有序数组转换为二叉树：

题目描述：

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵
平衡
二叉搜索树。

示例 1：
微信截图_20241202211515.png

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
微信截图_20241202211523.png

示例 2：

微信截图_20241202211530.png
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 按严格递增顺序排列
#二叉树的性质：二叉树的中序遍历一定是有序的，中序遍历一定是有序的二叉树一定是一个二叉搜索树。

思路：

所以这题是经典的二叉搜索树初始化题，一般做法就是找到有序数组中的中点以它为根节点两边为左右子树分别递归延展：微信截图_20241202211334.png

##如何说明这样做就能构建出平衡的二叉搜索树呢？请看证明：
微信截图_20241202212119.png

时间复杂度：

一共建立n个节点，每个节点时间消耗为O(1), 所以总的时间复杂度为O(n)

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return  build(nums, 0, nums.size() - 1);
    }
    TreeNode* build(vector<int>& nums, int l, int r)
    {
        if(l > r) return NULL;
        int mid = l + r >> 1; //以中间点为根节点
        auto root = new TreeNode(nums[mid]);
        root -> left = build(nums, l, mid - 1); //向左右两边展开左右子树
        root -> right = build(nums, mid + 1, r);
        return root;
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }
    TreeNode* build(vector<int>& nums, int l , int r)
    {
        if(l > r) return NULL;
        int mid = l + r >> 1;
        auto root = new TreeNode(nums[mid]);
        root -> left = build(nums, l, mid - 1);
        root -> right = build(nums, mid + 1, r);
        return root;
    }
};

LeetCode109.有序链表转换二叉搜索树：

题目描述：

给定一个单链表的头节点 head ，其中的元素按升序排序，将其转换为
平衡
二叉搜索树。

示例 1:

微信截图_20241203192630.png

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

提示:

head 中的节点数在[0, 2 * 10^4] 范围内
-10^5 <= Node.val <= 105

思路：

做法跟有序数组转换二叉搜索树一致，依旧是找到中间节点作为根节点向两边进行延展，但是不同于数组的索引，链表要找到中间节点需要每次遍历一遍链表统计链表长度，然后根据链表长度将指针往后移动大概(n - 1) / 2次，
这里输入以当前节点为头节点的链表之后，要对链表长度进行判断：
1.n = 1: 当前段的链表就只有当前节点一个了，那么直接创建当前节点即可
2.n > 1: 不止一个节点时就要取中间节点，划分左右子树，有n个节点的话，要取中间节点作为当前根节点，那么需要将指针往右移动，为了方便我们始终让左子树不为空，也就是有n个节点，让左子树拥有(n - 1) / 2 (上取整) 个节点，右子树则为 n - 1 - (n - 1) / 2(上取整)个节点，这样左子树无论如何都不为空，由于C++中的除法一般是下取整，所以使用图中公式可以将上取整变成下取整，这样一来循环上取整的(n / 2)次之后便是当前链表的中间节点，不过在递归时要将左子树的最后一个节点的后面（也就是中间节点的前一个位置）置为空节点，以将链表划分开，所以这里需要找到中间节点的前一个节点也就是上取整的(n / 2) - 1个节点

时间复杂度：

每次将区间划分为n / 2，以此类推，总共需要划分logn次，而每次还需遍历链表求长度n次，所以总共的时间复杂度是O(nlogn)
微信截图_20241203195151.png

注释代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return NULL;
        int n = 0;
        for(auto p = head; p; p = p -> next) n++; //当前段链表长度
        if(n == 1) return new TreeNode(head -> val); //当前段只有一个节点， 那么创建当前节点
        auto mid = head; //定义中间节点
        for(int i = 0; i < n / 2 - 1; i++) mid = mid -> next;  //获取中间节点前的节点
        auto root = new TreeNode(mid -> next -> val);  //将中间节点创建为当前根节点
        root -> right = sortedListToBST(mid -> next -> next);  //利用中间节点的下一个节点递归创建右子树
        mid -> next = NULL;  //将中间节点置为NULL，以将区间分段
        root -> left = sortedListToBST(head);  //从头节点开始递归创建左子树
        return root; //返回下一次递归的根节点
    }
};

纯享版：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return NULL;
        int n = 0;
        for(auto p = head; p; p = p -> next) n++;
        if(n == 1) return new TreeNode(head -> val);
        auto cur = head;
        for(int i = 0; i < n / 2 - 1; i++) cur = cur -> next;
        auto  root = new TreeNode(cur -> next -> val);
        root -> right = sortedListToBST(cur -> next -> next);
        cur -> next = NULL;
        root -> left = sortedListToBST(head);
        return root;
    }
};

LeetCode110.平衡二叉树：

题目描述：

给定一个二叉树，判断它是否是
平衡二叉树(平衡二叉树是指该树所有节点的左右子树的高度相差不超过 1。)

示例 1：
微信截图_20241203200949.png

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：
微信截图_20241203200958.png

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-10^4 <= Node.val <= 10^4

思路：

对于根节点来说，只要得出左右子树往下走的最大高度即可，跟二叉树的最大深度异曲同工，这里需要记录左子树的最大深度和右子树的最大深度，最终通过比较根节点下的左右子树高度差是否大于1
微信截图_20241203200702.png

时间复杂度：

每个节点会被遍历一次，所以时间复杂度是O(n)的

注释代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool ans; //定义一个标记
    bool isBalanced(TreeNode* root) {
        ans = true;
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root)
    {
        if(!root) return 0;
        int lh = dfs(root -> left), rh = dfs(root -> right); //递归求左右子树的最大高度
        if(abs(lh - rh) > 1) ans = false; //如果两边子树的高度差大于1那么置为false
        return max(lh, rh) + 1; //返回当前节点下的左右子树高度最大值+1（节点本身）
    }
};

纯享版：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool flag;
    bool isBalanced(TreeNode* root) {
        flag = true;
        dfs(root);
        return flag;
    }
    int dfs(TreeNode* root)
    {
        if(!root) return 0;
        
        int lh = dfs(root -> left), rh = dfs(root -> right);
        if(abs(lh - rh) > 1) flag = false;
        return max(lh, rh) + 1;
    }
};

*注：上述题解为acwing网站学习的题解代码，大多数图片是屏幕截图，仅用作交流学习，不作为商业用途。如有侵权，联系删除。

LeetCode 91~110题解

LeetCode91.解码方法：

题目描述：

思路：

时间复杂度：O(n)

注释代码：

纯享版：

LeetCode92.反转链表Ⅱ：

题目描述：

思路：

时间复杂度：O(n)

注释代码：

纯享版：

LeetCode93.复原IP地址：

题目描述：

思路：

时间复杂度：

注释代码：

纯享版：

LeetCode94.二叉树的中序遍历：

题目描述：

思路：

算法1： 递归做法

时间复杂度：O(n)

注释代码：

纯享版：

算法2: 迭代做法：

思路： 二叉搜索树一般迭代搜索方式：

时间复杂度：O(n)

注释代码：

纯享版：

2024/12/24二刷：

2025/1/7:

递归做法：

LeetCode95.不同的二叉搜索树Ⅱ：

题目描述：

思路：

时间复杂度：

注释代码：

纯享版：

LeetCode96.不同的二叉搜索树：

题目描述：

思路：

时间复杂度：O(n * n)

注释代码：

纯享版：

LeetCode97.交错字符串：

题目描述：

思路：

时间复杂度：O(n * n)

注释代码：

纯享版：

LeetCode98.验证二叉搜索树：

题目描述：

思路：

时间复杂度：

注释代码：

纯享版：

LeetCode99.恢复二叉树：

题目描述：

思路：

注释代码：

纯享版：

LeetCode100.相同的树：

题目描述：

思路：

时间复杂度：O(n)

注释代码：

纯享版：

LeetCode101.对称二叉树：

题目描述：

思路：

时间复杂度：O(n)

注释代码：

纯享版：

LeetCode102.二叉树的层序遍历：

题目描述：

思路：

时间复杂度：

注释代码：

算法1：递归做法

思路：二叉搜索树一般迭代搜索方式：