Python中链表的括号生成（Generate Parentheses）操作

2023-04-11 00:00:00 生成链表括号

链表生成括号是一个经典的递归问题。基本思路是在一个左括号数量等于右括号数量的前提下，每次递归可以选择添加左括号或右括号。根据这个思路，我们可以将问题转化为生成所有可能的括号组合。

下面是Python代码演示：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(p, left, right, parens=[]):
            if left:         # 如果还有左括号可以添加
                generate(p + '(', left-1, right)   # 添加一个左括号
            if right > left:    # 如果右括号数量小于左括号，表示可以添加右括号
                generate(p + ')', left, right-1)  # 添加一个右括号
            if not right:     # 如果没有未处理的右括号，表示已经生成完一个合法组合
                parens.append(p)
            return parens

        return generate('', n, n)

对于链表问题，我们可以把问题转化为树形结构。树的根节点表示为空序列，每个节点表示序列中添加一个括号，添加的括号有可能是左括号或右括号。左子节点表示添加左括号，右子节点表示添加右括号。

链表的生成过程实际上是在树形结构中寻找从根节点到叶子节点的所有路径。在这些路径中，左括号和右括号的数量都相等，且都等于链表长度一半。下面是使用链表的Python代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(left, right, path, result):
            if left == 0 and right == 0:   # 如果没有未处理的左右括号，表示已经生成完一个合法组合
                result.append(path)
                return 
            if left > 0:     # 如果还有左括号可以添加，添加左括号
                generate(left-1, right, path+'(', result)
            if right > left:   # 如果右括号数量小于左括号，表示可以添加右括号
                generate(left, right-1, path+')', result)

        result = []
        generate(n, n, '', result)
        return result

上面两段代码分别采用了链表和递归解决问题，两种解法都是使用了分治思想，把单个问题分解成多个子问题，最终合并这些子问题的解决方案。链表解法可能更容易理解，但是递归解法可以很自然地应用到其他问题中去。

相关文章