Concise python preorder recursive method, easy to understand with comments


  • 0
    H
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        def dfs(root):
            if not root:
                ans.append('#')
                return
            ans.append(str(root.val))
            dfs(root.left)
            dfs(root.right)
        ans = []
        dfs(root)
        return ' '.join(ans)
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def dfs(index):
            if data[index] == '#': return None, index
            root = TreeNode(int(data[index]))
            root.left, index = dfs(index+1)
            root.right, index = dfs(index+1)
            return root, index
        data = data.split()
        return dfs(0)[0]
    

    In both of two functions, I use dfs to implement preorder traversal in a recursive way. In deserialization part, index is used to record the current position of traversal.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.