Easy understanding Python Solution [preorder]


  • 0

    Inspiring by StefanPochmann's code

    Main Ideal:
    0 a recursive definition of preorder(T) is:
    preorder(T) = List(T.root) preorder(T.left) + + preorder(T.right)

    1 serialize Turns BT to String separate by ","

    2 deserialize Turns String to List using "," as delimiter
    and then turn List to BT recursively

    Noe: Treat List as Queue and always remove at front because Front is the Root

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Codec:
        def serialize(self, root):
            """Encodes a tree to a single string.
            
            :type root: TreeNode
            :rtype: str
            """
            ans = []
            self.TreeToString(root, ans)
            return ''.join(ans)
                
        #turn binary tree to string using pre-order    
        def TreeToString(self,root,ans):
            if root:
                ans.append(str(root.val) + ",")
                self.TreeToString(root.left,ans)
                self.TreeToString(root.right,ans)
            else:
                ans.append('NN'+",")
                
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            
            :type data: str
            :rtype: TreeNode
            """
            data = data.split(",")
            return self.StringToTree(data)
    
        # reconstruct binary tree from preorder
        def StringToTree(self,string):
            val = string.pop(0)
            if val == "NN":
                return None
            root = TreeNode(val)
            root.left = self.StringToTree(string)
            root.right = self.StringToTree(string)
            return root
    

Log in to reply
 

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