<jupyter_start><jupyter_text>[Unique Binary Search Trees II](https://leetcode.com/problems/unique-binary-search-trees-ii/)。给定长度为$n$的正数序列$[1,2,...,n]$，求所有可能的BST结构。思路：递归。因为给的是有序的正数序列，任意选取一个数字作为根节点，则左分支就为该数字左边的数字，而右分支为其右边的数字。设计一个递归函数```rec(i,j)```，其会返回$[i,j]$之间数字可能构成的所有BST。<jupyter_code>def generateTrees(n: int):
    def rec(i, j):
        if i > j:
            return [None]
        if i == j:
            return [TreeNode(i)]

        res = list()
        for root_val in range(i, j+1):
            left_branches = rec(i, root_val-1)
            right_branches = rec(root_val+1, j)

            for left_branch in left_branches:
                for right_branch in right_branches:
                    root = TreeNode(root_val)
                    root.left = left_branch
                    root.right = right_branch
                    res.append(root)

        return res

    return rec(1, n) if n >= 1 else list()<jupyter_output><empty_output><jupyter_text>[Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)。**2019百度面试手撕代码题**。给一二叉树与两个节点，返回两节点的最低公共祖先。思路：设计一个递归函数，基准情况如下。若根节点空则返回空，若两节点之一是根节点，则返回根节点。然后递归地在左右分支中查找LCA。如果左分支返回不为空，则说明左分支至少包含两节点中的一个，右边也一样。若左右返回都不为空，说明两节点分属于左右分支，则当前根节点是一个LCA。<jupyter_code>def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if root is None:
        return None

    if root == p or root == q:
        return root

    left_LCA = lowestCommonAncestor(root.left, p, q)
    right_LCA = lowestCommonAncestor(root.right, p, q)

    if left_LCA and right_LCA:
        return root
    elif left_LCA:
        return left_LCA
    else:
        return right_LCA<jupyter_output><empty_output><jupyter_text>[Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/)。有序数组转平衡搜索二叉树。思路：递归。要想生成的二叉搜索树平衡，那么每次将数组的中间元素作为根节点生成树即可。<jupyter_code>def sortedArrayToBST(nums) -> TreeNode:
    if not nums:
        return None

    n = len(nums)
    if n == 1:
        return TreeNode(nums[0])

    mid = (n-1) >> 1
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])

    return root<jupyter_output><empty_output><jupyter_text>[Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/)。有序单链表转平衡搜索二叉树。思路：链表转数组，再递归。<jupyter_code>def sortedListToBST(head: ListNode) -> TreeNode:
    def ll2l(head):    # linked list to list
        nums = list()
        while head:
            nums.append(head.val)
            head = head.next
        return nums

    def l2bst(nums):
        if not nums:
            return None
        n = len(nums)
        if n == 1:
            return TreeNode(nums[0])

        mid = (n-1) >> 1
        root = TreeNode(nums[mid])
        root.left = l2bst(nums[:mid])
        root.right = l2bst(nums[mid+1:])

        return root

    nums = ll2l(head)
    return l2bst(nums)<jupyter_output><empty_output><jupyter_text>[Construct Binary Tree from Inorder and Postorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)。由中序序列与后序序列重构二叉树。思路：递归。后序遍历的最后一个节点为根节点，中序遍历左右划分后分别是左右子树。<jupyter_code>def buildTree(inorder, postorder) -> TreeNode:
    if not postorder:
        return None
    if len(postorder) == 1:
        return TreeNode(postorder[0])

    root_node = TreeNode(postorder[-1])
    root_in_idx = inorder.index(root_node.val)
    left_branch = buildTree(inorder[:root_in_idx],
                            postorder[:root_in_idx])
    right_branch = buildTree(inorder[root_in_idx+1:],
                             postorder[root_in_idx:-1])
    root_node.left = left_branch
    root_node.right = right_branch

    return root_node<jupyter_output><empty_output><jupyter_text>[Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)。给定一棵二叉树的先序序列跟中序序列，重构这颗二叉树，返回根节点。思路：递归。<jupyter_code>def buildTree(preorder, inorder) -> TreeNode:
    if not preorder:
        return None
    if len(preorder) == 1:
        return TreeNode(preorder[0])

    root_val = preorder[0]
    root_in_idx = inorder.index(root_val)
    root = TreeNode(root_val)

    left_branch = buildTree(preorder[1:root_in_idx+1], inorder[:root_in_idx])
    right_branch = buildTree(preorder[root_in_idx+1:], inorder[root_in_idx+1:])

    root.left = left_branch
    root.right = right_branch

    return root<jupyter_output><empty_output><jupyter_text>[Maximum Binary Tree](https://leetcode.com/problems/maximum-binary-tree/)。给一数组，将该数组转换成二叉树。每次将数组的最大值作为根节点，左边的数字称为左分支，右边的数字称为右分支。思路：每次递归找到最大值与最大值对应的索引，以该索引划分数组，左边递归右边递归即可。<jupyter_code>def constructMaximumBinaryTree(nums) -> TreeNode:
    if not nums:
        return None

    max_val = max(nums)
    max_idx = nums.index(max_val)

    root = TreeNode(max_val)
    root.left = self.constructMaximumBinaryTree(nums[:max_idx])
    root.right = self.constructMaximumBinaryTree(nums[max_idx+1:])

    return root<jupyter_output><empty_output><jupyter_text>[Longest Substring with At Least K Repeating Characters](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/)。寻找一个最长字符串的长度，该字串中每一个字符都至少出现$k$次。思路：首先对字串的每一个字符进行计数，若所有字符的出现次数均大于等于$k$则直接返回字串的长度。若有不满足条件的字符，则该字符是不可能被包含的，所以以这些字符为界来分割原字串，在对字串进行递归求解，返回最大值即可。<jupyter_code>def longestSubstring(s: str, k: int) -> int:
    n = len(s)
    cnt_lookup = dict()

    for ch in s:
        cnt_lookup.setdefault(ch, 0)
        cnt_lookup[ch] += 1

    for ch in cnt_lookup:
        if cnt_lookup[ch] < k:
            return max([longestSubstring(sub_s, k) for sub_s in s.split(ch)])

    return n<jupyter_output><empty_output><jupyter_text>[Different Ways to Add Parentheses](https://leetcode.com/problems/different-ways-to-add-parentheses/)。以字串形式给出一个运算式，尝试所有合法的加括号方式，返回所有情况下的运算结果。思路：设置一个函数，它会返回一个表达式在不同优先级下所有可能的解。那么基准情况就是空字串或者单数字，前者返回空，后者直接返回单数字列表。因为加括号是一个连续区域，并且对每一个运算符的两端都可以括起来成一个表达式，所以递归时扫描所有运算符，对运算符两边的表达式进行递归。<jupyter_code>def diffWaysToCompute(exp: str) -> List[int]:
    if not exp:
        return None
    if exp.isdigit():
        return [int(exp)]

    res = list()
    n = len(exp)
    for i, ch in enumerate(exp):
        if ch in ['+', '-', '*']:
            left_res = diffWaysToCompute(exp[:i])
            right_res = diffWaysToCompute(exp[i+1:])

            for l_res in left_res:
                for r_res in right_res:
                    if ch == '+':
                        res.append(l_res+r_res)
                    elif ch == '-':
                        res.append(l_res-r_res)
                    else:
                        res.append(l_res*r_res)

    return res<jupyter_output><empty_output><jupyter_text>[Same Tree](https://leetcode.com/problems/same-tree/)。给两颗二叉树，判断两二叉树是否相同。思路：递归。基准情况为两棵树都为空时一定相同，其中一颗为空或者值不相等时返回False。值相等且存在子树时，必须满足左子树相同且右子树也相同。<jupyter_code>def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    if not p and not q:
        return True
    elif not p or not q or p.val != q.val:
        return False
    else:
        return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)<jupyter_output><empty_output><jupyter_text>[Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/)。给两棵非空树$s$和$t$，判断$t$是不是$s$的子树。思路：如果$t$是$s$的子树，那么在$s$中肯定存在一个节点$root$使得$root$与$t$是相同的两棵树，所以可以使用上题的函数来判断两棵树是否相同。那么剩下的问题就是怎么找到$root$，首先判断$s$是否与$t$相同，然后递归地比较$s.left$或者$s.right$是否与$t$相同。<jupyter_code>def isSubtree(s: TreeNode, t: TreeNode) -> bool:
    def isSameTree(root_1, root_2):
        if not root_1 and not root_2:
            return True
        elif not root_1 or not root_2 or root_1.val != root_2.val:
            return False
        else:
            return isSameTree(root_1.left, root_2.left) and isSameTree(root_1.right, root_2.right)

    if not s:
        return False
    elif isSameTree(s, t):
        return True
    else:
        return isSubtree(s.left, t) or isSubtree(s.right, t)<jupyter_output><empty_output><jupyter_text>[Pow(x, n)](https://leetcode.com/problems/powx-n/)。尽可能高效的实现一个乘方运算。思路：递归，基准情况，指数为$0$返回1，指数为$1$返回自身。递推式为：$$\begin{align}x^{n}=\begin{cases}& x^{n/2}\times{x^{n/2}}, n为偶数 \\& x\times{x^{(n-1)/2}\times{x^{(n-1)/2}}}, n为奇数 \\\end{cases}\end{align}$$<jupyter_code>def myPow(x: float, n: int) -> float:
    if n < 0:
        return myPow(1/x, -n)
    if n == 0:
        return 1
    if n == 1:
        return x

    if n & 1 == 0:
        return myPow(x, n >> 1)*myPow(x, n >> 1)
    else:
        return x*myPow(x, n >> 1)*myPow(x, n >> 1)<jupyter_output><empty_output><jupyter_text>[Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)。判别平衡二叉树。思路：设计一个递归函数返回当前节点的最大深度，但是返回深度是有条件的。平衡树需要满足每一个子树都是平衡树，所以返回深度的条件就是必须是平衡树。<jupyter_code>def isBalanced(root: TreeNode) -> bool:
    def rec(root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1

        left = rec(root.left)
        right = rec(root.right)
        if left == -1 or right == -1:
            return -1

        return max(left, right)+1 if abs(left-right) < 2 else -1

    if not root:
        return True

    return rec(root) != -1<jupyter_output><empty_output><jupyter_text>[后序序列的合法性](https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&&tqId=11176&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking)。给一数组，判断该序列是否是BST的后序序列。(该题的空测试用例很费解，竟然让返回False，这里就不管了)思路：后序序列的尾元素就是根节点，那么之前的序列可分为两部分，小于根节点的左分支与大于根节点的右分支。<jupyter_code>def VerifySquenceOfBST(sequence):
    n = len(sequence)
    if n == 0:
        return True

    root = sequence[-1]
    for i in range(n):
        if sequence[i] >= sequence[-1]:
            break

    for j in range(i, n):    # 右边的值应该都大于根节点
        if sequence[j] < root:
            return False

    return True if VerifySquenceOfBST(sequence[:i]) and VerifySquenceOfBST(sequence[i+1:]) else False<jupyter_output><empty_output><jupyter_text>[树的子结构](https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=1)。给两棵树```pRoot1```跟```pRoot2```，判断```pRoot2```是否是```pRoot1```的一个子结构。令空树不是任何树的子结构。思路：第一步需要先找到根节点相等的位置，第二步开始递归比较。<jupyter_code>def HasSubtree(pRoot1, pRoot2):
    def rec(root1, root2):
        if not root2:
            return True
        if not root1 or root1.val != root2.val:
            return False
        return rec(root1.left, root2.left) and rec(root1.right, root2.right)

    if not pRoot1 or not pRoot2:    # 二者有一空则返回False
        return False

    return rec(pRoot1, pRoot2) or \
        HasSubtree(pRoot1.left, pRoot2) or \
        HasSubtree(pRoot1.right, pRoot2)<jupyter_output><empty_output><jupyter_text>[Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)。指定括号对的数量$n$，求所有可能合法的括号序列。思路：设$left$、$right$分别为左右括号的数量，在生成过程中，要始终保证$left\ge{right}$。若$left<n$则可以添加左括号，若$right<left$则可以添加右括号。但是注意，对能否添加左括号的判断要优先与对右括号的判断。<jupyter_code>def generateParenthesis(n: int):
    res = list()

    def rec(cur_res, left, right):
        if len(cur_res) == 2*n:
            res.append(cur_res)
            return

        if left < n:    # 能否添加左括号
            rec(cur_res+'(', left+1, right)
        if left > right:    # 能否添加右括号
            rec(cur_res+')', left, right+1)

    rec(str(), 0, 0)
    return res<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12900122441840126, 'fraction_numerical': 0.015829980759139408, 'mean_word_length': 3.3678380443086327, 'pattern_counts': {'":': 0, '<': 72, '<?xml version=': 0, '>': 94, 'https://': 16, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '16', 'dir': 'jupyter-structured-clean-dedup', 'id': '590840', 'license': 'MIT', 'n_tokens_mistral': 5240, 'n_tokens_neox': 5440, 'n_words': 667, 'path': 'Algorithm/BlankBoard/.ipynb_checkpoints/Recursion-checkpoint.ipynb', 'repo_name': 'Daya-Jin/DataStructureAndAlgorithm', 'size': '11434'}