当前位置：首页 > article >正文

Leetcode: 0091-0099题速览

article 2024/12/23 4:14:52

Leetcode: 0091-0099题速览

本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

遵从开源协议为知识共享版权归属-相同方式共享 4.0 国际公共许可证

研一在读备战就业，制此集合便于空闲时间浏览，有任何疑惑问题欢迎讨论，共同进步

Leetcode: 0091-0099题速览
- [91. 解码方法](https://leetcode.cn/problems/decode-ways)
- - 题目描述
  - 解法
  - - 方法一：动态规划
    - - Python3
      - Java
      - C++
- [92. 反转链表 II](https://leetcode.cn/problems/reverse-linked-list-ii)
- - 题目描述
  - 解法
  - - 方法一：模拟
    - - Python3
      - Java
      - C++
- [93. 复原 IP 地址](https://leetcode.cn/problems/restore-ip-addresses)
- - 题目描述
  - 解法
  - - 方法一：DFS
    - - Python3
      - Java
      - C++
- [94. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal)
- - 题目描述
  - 解法
  - - 方法一：递归遍历
    - - Python3
      - Java
      - C++
- [95. 不同的二叉搜索树 II](https://leetcode.cn/problems/unique-binary-search-trees-ii)
- - 题目描述
  - 解法
  - - 方法一：DFS
    - - Python3
      - Java
      - C++
- [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees)
- - 题目描述
  - 解法
  - - 方法一：动态规划
    - - Python3
      - Java
      - C++
- [97. 交错字符串](https://leetcode.cn/problems/interleaving-string)
- - 题目描述
  - 解法
  - - 方法一：记忆化搜索
    - - Python3
      - Java
      - C++
- [98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree)
- - 题目描述
  - 解法
  - - 方法一：递归
    - - Python3
      - Java
      - C++
- [99. 恢复二叉搜索树](https://leetcode.cn/problems/recover-binary-search-tree)
- - 题目描述
  - 解法
  - - 方法一：中序遍历
    - - Python3
      - Java
      - C++

91. 解码方法

题目描述

一条包含字母 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 只包含数字，并且可能包含前导零。

难度：中等

标签：字符串,动态规划

解法

方法一：动态规划

我们定义 $f [i]$ 表示字符串的前 $i$ 个字符的解码方法数，初始时 $f [0] = 1$ ，其余 $f [i] = 0$ 。

考虑 $f [i]$ 如何进行状态转移。

如果第 $i$ 个字符（即 $s [i - 1]$ ）单独形成编码，那么它对应一种解码方式，即 $f [i] = f [i - 1]$ 。前提是 $\neq 0$ 。
如果第 $i - 1$ 个字符和第 $i$ 个字符组成的字符串在 $[1, 26]$ 范围内，那么它们可以作为一个整体，对应一种解码方式，即 $f [i] = f [i] + f [i - 2]$ 。前提是 $\neq 0$ ，且 $s [i - 2] s [i - 1]$ 在 $[1, 26]$ 范围内。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是字符串的长度。

Python3

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        f = [1] + [0] * n
        for i, c in enumerate(s, 1):
            if c != "0":
                f[i] = f[i - 1]
            if i > 1 and s[i - 2] != "0" and int(s[i - 2 : i]) <= 26:
                f[i] += f[i - 2]
        return f[n]

Java

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] = f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && Integer.valueOf(s.substring(i - 2, i)) <= 26) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

C++

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        int f[n + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] != '0') {
                f[i] = f[i - 1];
            }
            if (i > 1 && (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] <= '6')) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};

92. 反转链表 II

题目描述

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

示例 1：

在这里插入图片描述

输入：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

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

难度：中等

标签：链表

解法

方法一：模拟

定义一个虚拟头结点 dummy，指向链表的头结点 head，然后定义一个指针 pre 指向 dummy，从虚拟头结点开始遍历链表，遍历到第 left 个结点时，将 pre 指向该结点，然后从该结点开始遍历 right - left + 1 次，将遍历到的结点依次插入到 pre 的后面，最后返回 dummy.next 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为链表的长度。

Python3

## Definition for singly-linked list.
## class ListNode:
##     def __init__(self, val=0, next=None):
##         self.val = val
##         self.next = next
class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], left: int, right: int
    ) -> Optional[ListNode]:
        if head.next is None or left == right:
            return head
        dummy = ListNode(0, head)
        pre = dummy
        for _ in range(left - 1):
            pre = pre.next
        p, q = pre, pre.next
        cur = q
        for _ in range(right - left + 1):
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        p.next = pre
        q.next = cur
        return dummy.next

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head.next == null || left == right) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; ++i) {
            pre = pre.next;
        }
        ListNode p = pre;
        ListNode q = pre.next;
        ListNode cur = q;
        for (int i = 0; i < right - left + 1; ++i) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        p.next = pre;
        q.next = cur;
        return dummy.next;
    }
}

C++

/**
 * 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 left, int right) {
        if (!head->next || left == right) {
            return head;
        }
        ListNode* dummy = new ListNode(0, head);
        ListNode* pre = dummy;
        for (int i = 0; i < left - 1; ++i) {
            pre = pre->next;
        }
        ListNode *p = pre, *q = pre->next;
        ListNode* cur = q;
        for (int i = 0; i < right - left + 1; ++i) {
            ListNode* t = cur->next;
            cur->next = pre;
            pre = cur;
            cur = t;
        }
        p->next = pre;
        q->next = cur;
        return dummy->next;
    }
};

93. 复原 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 仅由数字组成

难度：中等

标签：字符串,回溯

解法

方法一：DFS

我们定义一个函数 $df s (i)$ ，表示从字符串 $s$ 的第 $i$ 位开始，搜索能够组成的 IP 地址列表。

函数 $df s (i)$ 的执行步骤如下：

如果 $i$ 大于等于字符串 $s$ 的长度，说明已经完成了四段 IP 地址的拼接，判断是否满足四段 IP 地址的要求，如果满足则将当前 $I P$ 加入答案。

如果 $i$ 小于字符串 $s$ 的长度，此时还需要拼接 $I P$ 地址的一段，此时需要确定这一段 $I P$ 地址的值。如果该值大于 $255$ ，或者当前位置 $i$ 为 $0$ 且 $i$ 之后的若干位的数值大于 $0$ ，则说明不满足要求，直接返回。否则，将其加入 $I P$ 地址列表，并继续搜索下一段 $I P$ 地址。

时间复杂度 $\times 3^4)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

Python3

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def check(i: int, j: int) -> int:
            if s[i] == "0" and i != j:
                return False
            return 0 <= int(s[i : j + 1]) <= 255

        def dfs(i: int):
            if i >= n and len(t) == 4:
                ans.append(".".join(t))
                return
            if i >= n or len(t) >= 4:
                return
            for j in range(i, min(i + 3, n)):
                if check(i, j):
                    t.append(s[i : j + 1])
                    dfs(j + 1)
                    t.pop()

        n = len(s)
        ans = []
        t = []
        dfs(0)
        return ans

Java

class Solution {
    private int n;
    private String s;
    private List<String> ans = new ArrayList<>();
    private List<String> t = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        n = s.length();
        this.s = s;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i >= n && t.size() == 4) {
            ans.add(String.join(".", t));
            return;
        }
        if (i >= n || t.size() >= 4) {
            return;
        }
        int x = 0;
        for (int j = i; j < Math.min(i + 3, n); ++j) {
            x = x * 10 + s.charAt(j) - '0';
            if (x > 255 || (s.charAt(i) == '0' && i != j)) {
                break;
            }
            t.add(s.substring(i, j + 1));
            dfs(j + 1);
            t.remove(t.size() - 1);
        }
    }
}

C++

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int n = s.size();
        vector<string> ans;
        vector<string> t;
        function<void(int)> dfs = [&](int i) {
            if (i >= n && t.size() == 4) {
                ans.push_back(t[0] + "." + t[1] + "." + t[2] + "." + t[3]);
                return;
            }
            if (i >= n || t.size() >= 4) {
                return;
            }
            int x = 0;
            for (int j = i; j < min(n, i + 3); ++j) {
                x = x * 10 + s[j] - '0';
                if (x > 255 || (j > i && s[i] == '0')) {
                    break;
                }
                t.push_back(s.substr(i, j - i + 1));
                dfs(j + 1);
                t.pop_back();
            }
        };
        dfs(0);
        return ans;
    }
};

94. 二叉树的中序遍历

题目描述

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

示例 1：

在这里插入图片描述

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

示例 2：

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

示例 3：

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

提示：

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

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

难度：简单

标签：栈,树,深度优先搜索,二叉树

解法

方法一：递归遍历

我们先递归左子树，再访问根节点，接着递归右子树。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。

Python3

## Definition for a binary tree node.
## class TreeNode:
##     def __init__(self, val=0, left=None, right=None):
##         self.val = val
##         self.left = left
##         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<Integer> ans = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        ans.add(root.val);
        dfs(root.right);
    }
}

C++

/**
 * 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> ans;
        function<void(TreeNode*)> dfs = [&](TreeNode* root) {
            if (!root) {
                return;
            }
            dfs(root->left);
            ans.push_back(root->val);
            dfs(root->right);
        };
        dfs(root);
        return ans;
    }
};

95. 不同的二叉搜索树 II

题目描述

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

示例 1：

在这里插入图片描述

输入：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

难度：中等

标签：树,二叉搜索树,动态规划,回溯,二叉树

解法

方法一：DFS

我们设计一个函数 $df s (i, j)$ ，返回由 $[i, j]$ 组成的所有可行的二叉搜索树，那么答案就是 $df s (1, n)$ 。

函数 $df s (i, j)$ 的执行步骤如下：

如果 $i > j$ ，那么说明此时没有数字可以构成二叉搜索树，返回由一个空节点组成的列表。
如果 $\leq j$ ，那么我们枚举 $[i, j]$ 中的数字 $v$ 作为根节点，那么根节点 $v$ 的左子树由 $[i, v - 1]$ 组成，右子树由 $[v + 1, j]$ 组成，最后将左右子树的所有组合笛卡尔积，即 $left \times right$ ，加上根节点 $v$ ，得到以 $v$ 为根节点的所有二叉搜索树。

时间复杂度 $\times G(n))$ ，空间复杂度 $\times G(n))$ 。其中 $G (n)$ 是卡特兰数。

Python3

## Definition for a binary tree node.
## class TreeNode:
##     def __init__(self, val=0, left=None, right=None):
##         self.val = val
##         self.left = left
##         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def dfs(i: int, j: int) -> List[Optional[TreeNode]]:
            if i > j:
                return [None]
            ans = []
            for v in range(i, j + 1):
                left = dfs(i, v - 1)
                right = dfs(v + 1, j)
                for l in left:
                    for r in right:
                        ans.append(TreeNode(v, l, r))
            return ans

        return dfs(1, n)

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        return dfs(1, n);
    }

    private List<TreeNode> dfs(int i, int j) {
        List<TreeNode> ans = new ArrayList<>();
        if (i > j) {
            ans.add(null);
            return ans;
        }
        for (int v = i; v <= j; ++v) {
            var left = dfs(i, v - 1);
            var right = dfs(v + 1, j);
            for (var l : left) {
                for (var r : right) {
                    ans.add(new TreeNode(v, l, r));
                }
            }
        }
        return ans;
    }
}

C++

/**
 * 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) {
        function<vector<TreeNode*>(int, int)> dfs = [&](int i, int j) {
            if (i > j) {
                return vector<TreeNode*>{nullptr};
            }
            vector<TreeNode*> ans;
            for (int v = i; v <= j; ++v) {
                auto left = dfs(i, v - 1);
                auto right = dfs(v + 1, j);
                for (auto l : left) {
                    for (auto r : right) {
                        ans.push_back(new TreeNode(v, l, r));
                    }
                }
            }
            return ans;
        };
        return dfs(1, n);
    }
};

96. 不同的二叉搜索树

题目描述

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

示例 1：

在这里插入图片描述

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

难度：中等

标签：树,二叉搜索树,数学,动态规划,二叉树

解法

方法一：动态规划

我们定义 $f [i]$ 表示 $[1, i]$ 能产生的二叉搜索树的个数，初始时 $f [0] = 1$ ，答案为 $f [n]$ 。

我们可以枚举节点数 $i$ ，那么左子树节点数 $\in [0, i - 1]$ ，右子树节点数 $k = i - j - 1$ ，左子树节点数和右子树节点数的组合数为 $\times f[k]$ ，因此 $\sum_{j = 0}^{i - 1} f[j] \times f[i - j - 1]$ 。

最后返回 $f [n]$ 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为节点数。

Python3

class Solution:
    def numTrees(self, n: int) -> int:
        f = [1] + [0] * n
        for i in range(n + 1):
            for j in range(i):
                f[i] += f[j] * f[i - j - 1]
        return f[n]

Java

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

C++

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 = 0; j < i; ++j) {
                f[i] += f[j] * f[i - j - 1];
            }
        }
        return f[n];
    }
};

97. 交错字符串

题目描述

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

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

s = s₁ + s₂ + ... + s_n
t = t₁ + t₂ + ... + t_m
|n - m| <= 1
交错是 s₁ + t₁ + s₂ + t₂ + s₃ + t₃ + ... 或者 t₁ + s₁ + t₂ + s₂ + t₃ + s₃ + ...

注意：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) 额外的内存空间来解决它?

难度：中等

标签：字符串,动态规划

解法

方法一：记忆化搜索

我们记字符串 $s_1$ 的长度为 $m$ ，字符串 $s_2$ 的长度为 $n$ ，如果 $\neq |s_3|$ ，那么 $s_3$ 一定不是 $s_1$ 和 $s_2$ 的交错字符串，返回 false。

接下来，我们设计一个函数 $df s (i, j)$ ，表示从 $s_1$ 的第 $i$ 个字符和 $s_2$ 的第 $j$ 个字符开始，能否交错组成 $s_3$ 的剩余部分。那么答案就是 $df s (0, 0)$ 。

函数 $df s (i, j)$ 的计算过程如下：

如果 $\geq m$ 并且 $\geq n$ ，那么说明 $s_1$ 和 $s_2$ 都已经遍历完毕，返回 true。

如果 $i < m$ 并且 $s_1[i] = s_3[i + j]$ ，那么说明 $s_1[i]$ 这个字符是 $s_3[i + j]$ 中的一部分，因此递归地调用 $df s (i + 1, j)$ 判断 $s_1$ 的下一个字符能否和 $s_2$ 的当前字符匹配，如果能匹配成功，就返回 true。

同理，如果 $j < n$ 并且 $s_2[j] = s_3[i + j]$ ，那么说明 $s_2[j]$ 这个字符是 $s_3[i + j]$ 中的一部分，因此递归地调用 $df s (i, j + 1)$ 判断 $s_2$ 的下一个字符能否和 $s_1$ 的当前字符匹配，如果能匹配成功，就返回 true。

否则，返回 false。

为了避免重复计算，我们可以使用记忆化搜索。

时间复杂度 $\times n)$ ，空间复杂度 $\times n)$ 。其中 $m$ 和 $n$ 分别是字符串 $s_1$ 和 $s_2$ 的长度。

Python3

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i >= m and j >= n:
                return True
            k = i + j
            if i < m and s1[i] == s3[k] and dfs(i + 1, j):
                return True
            if j < n and s2[j] == s3[k] and dfs(i, j + 1):
                return True
            return False

        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        return dfs(0, 0)

Java

class Solution {
    private Map<List<Integer>, Boolean> f = new HashMap<>();
    private String s1;
    private String s2;
    private String s3;
    private int m;
    private int n;

    public boolean isInterleave(String s1, String s2, String s3) {
        m = s1.length();
        n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        this.s1 = s1;
        this.s2 = s2;
        this.s3 = s3;
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        if (i >= m && j >= n) {
            return true;
        }
        var key = List.of(i, j);
        if (f.containsKey(key)) {
            return f.get(key);
        }
        int k = i + j;
        boolean ans = false;
        if (i < m && s1.charAt(i) == s3.charAt(k) && dfs(i + 1, j)) {
            ans = true;
        }
        if (!ans && j < n && s2.charAt(j) == s3.charAt(k) && dfs(i, j + 1)) {
            ans = true;
        }
        f.put(key, ans);
        return ans;
    }
}

C++

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

98. 验证二叉搜索树

题目描述

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

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

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

示例 1：

在这里插入图片描述

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

示例 2：

在这里插入图片描述

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

提示：

树中节点数目范围在[1, 10⁴] 内
-2³¹ <= Node.val <= 2³¹ - 1

难度：中等

标签：树,深度优先搜索,二叉搜索树,二叉树

解法

方法一：递归

我们可以对二叉树进行递归中序遍历，如果遍历到的结果是严格升序的，那么这棵树就是一个二叉搜索树。

因此，我们使用一个变量 $\textit{prev}$ 来保存上一个遍历到的节点，初始时 $\textit{prev} = -\infty$ ，然后我们递归遍历左子树，如果左子树不是二叉搜索树，直接返回 $\textit{False}$ ，否则判断当前节点的值是否大于 $\textit{prev}$ ，如果不是，返回 $\textit{False}$ ，否则更新 $\textit{prev}$ 为当前节点的值，然后递归遍历右子树。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点个数。

Python3

## Definition for a binary tree node.
## class TreeNode:
##     def __init__(self, val=0, left=None, right=None):
##         self.val = val
##         self.left = left
##         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(root: Optional[TreeNode]) -> bool:
            if root is None:
                return True
            if not dfs(root.left):
                return False
            nonlocal prev
            if prev >= root.val:
                return False
            prev = root.val
            return dfs(root.right)

        prev = -inf
        return dfs(root)

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode prev;

    public boolean isValidBST(TreeNode root) {
        return dfs(root);
    }

    private boolean dfs(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!dfs(root.left)) {
            return false;
        }
        if (prev != null && prev.val >= root.val) {
            return false;
        }
        prev = root;
        return dfs(root.right);
    }
}

C++

/**
 * 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) {
        TreeNode* prev = nullptr;
        function<bool(TreeNode*)> dfs = [&](TreeNode* root) {
            if (!root) {
                return true;
            }
            if (!dfs(root->left)) {
                return false;
            }
            if (prev && prev->val >= root->val) {
                return false;
            }
            prev = root;
            return dfs(root->right);
        };
        return dfs(root);
    }
};

99. 恢复二叉搜索树

题目描述

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

示例 1：

在这里插入图片描述

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

示例 2：

在这里插入图片描述

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

提示：

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

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

难度：中等

标签：树,深度优先搜索,二叉搜索树,二叉树

解法

方法一：中序遍历

中序遍历二叉搜索树，得到的序列是递增的。如果有两个节点的值被错误地交换，那么中序遍历得到的序列中，一定会出现两个逆序对。我们用 first 和 second 分别记录这两个逆序对中较小值和较大值的节点，最后交换这两个节点的值即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉搜索树的节点个数。

Python3

## Definition for a binary tree node.
## class TreeNode:
##     def __init__(self, val=0, left=None, right=None):
##         self.val = val
##         self.left = left
##         self.right = right
class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        def dfs(root):
            if root is None:
                return
            nonlocal prev, first, second
            dfs(root.left)
            if prev and prev.val > root.val:
                if first is None:
                    first = prev
                second = root
            prev = root
            dfs(root.right)

        prev = first = second = None
        dfs(root)
        first.val, second.val = second.val, first.val

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode prev;
    private TreeNode first;
    private TreeNode second;

    public void recoverTree(TreeNode root) {
        dfs(root);
        int t = first.val;
        first.val = second.val;
        second.val = t;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (prev != null && prev.val > root.val) {
            if (first == null) {
                first = prev;
            }
            second = root;
        }
        prev = root;
        dfs(root.right);
    }
}

C++

/**
 * 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* prev = nullptr;
        TreeNode* first = nullptr;
        TreeNode* second = nullptr;
        function<void(TreeNode * root)> dfs = [&](TreeNode* root) {
            if (!root) return;
            dfs(root->left);
            if (prev && prev->val > root->val) {
                if (!first) first = prev;
                second = root;
            }
            prev = root;
            dfs(root->right);
        };
        dfs(root);
        swap(first->val, second->val);
    }
};