Study Plan For Algorithms - Part47

1. 复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。

class Solution:
    def restoreIpAddresses(self, s):
        def valid(segment):
            return int(segment) <= 255 if segment[0]!= "0" else len(segment) == 1

        def dfs(start, path):
            if len(path) == 4 and start == len(s):
                res.append(".".join(path))
                return
            for i in range(start, min(start + 3, len(s))):
                segment = s[start:i + 1]
                if valid(segment):
                    dfs(i + 1, path + [segment])

        res = []
        dfs(0, [])
        return res

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

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        def inorder(node):
            if node:
                inorder(node.left)
                result.append(node.val)
                inorder(node.right)
        inorder(root)
        return result