inorder dfs serialization & interative with stack for deserialization


  • 0
    D
    class Codec:
    
        def serialize(self, root):
            """Encodes a tree to a single string.
            
            :type root: TreeNode
            :rtype: str
            """
            def preorder(root):
                if not root:
                    res.append('#')
                else:
                    res.append(str(root.val))
                    preorder(root.left)
                    preorder(root.right)
            res = []
            preorder(root)
            return ','.join(res)
            
    
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            
            :type data: str
            :rtype: TreeNode
            """
            root = TreeNode(0)
            stack, data = [root], data.split(',')
            i = 0
            while i < len(data):
                node = TreeNode(int(data[i])) if data[i] != '#' else None
                if node is None:
                    i += 1
                    while i < len(data) and data[i] == '#':
                        stack.pop()
                        i += 1
                    if i == len(data):
                        break
                    parent = stack.pop()
                    right_child = TreeNode(int(data[i])) if data[i] != '#' else None
                    parent.right = right_child
                    stack.append(right_child)
                else:
                    stack[-1].left = node
                    stack.append(node)
                i += 1
            return root.left
    

Log in to reply
 

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