How do I make TreeNode from list by Python

Question

Lately, I started "leetcode" for studying programming. Sometimes, I encounter the question which is related to TreeNode. https://leetcode.com/problems/longest-univalue-path/

I usually run code in local to make sure if my code work. But those questions require me to prepare for TreeNode in advance, otherwise, I can not run in local. I don't know how to build TreeNode from a list.

I want to make TreeNode from a list by Python, like here.

class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

input: [5,4,5,1,1,5]

output:
TreeNode{val: 5, left: TreeNode{val: 4, left: TreeNode{val: 1, left: None, right: None}, right: TreeNode{val: 1, left: None, right: None}}, right: TreeNode{val: 5, left: TreeNode{val: 5, left: None, right: None}, right: None}}

I know we can make sure whether the code work or not on leetcode. However, I think it's slow for me to check the code on leetcode. I would like to run my code in local. I hope you will help me.

In your output, you have 5 nodes: 5, 4, 1, 1, 5. However, you have 6 nodes in your input: 5, 4, 5, 1, 1, 5. Is this a typo? — aiyan, Nov 16 '19 at 23:37
Possible duplicate of [How to Implement a Binary Tree?](https://stackoverflow.com/questions/2598437/how-to-implement-a-binary-tree) — kaya3, Nov 17 '19 at 00:01

score 1 · Answer 1 · answered Nov 17 '19 at 00:20

Take a look at LeetCode's official explanation https://support.leetcode.com/hc/en-us/articles/360011883654-What-does-1-null-2-3-mean-in-binary-tree-representation- of how their serialized formatting of a binary tree into the kind of list you see in their test cases works. If you want to run your solution against those test cases locally, you'll also need to write some code (or I'm sure you can find some online) that will input a serialized list, build the tree, and return the tree's root TreeNode so you can pass it to your find_longest_univalue_path function.

score 1 · Answer 2 · answered Nov 02 '20 at 07:06

Guess this is what you need:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
def creatBTree(data, index):
    pNode = None
    if index < len(data):
        if data[index] == None:
            return
        pNode = TreeNode(data[index])
        pNode.left = creatBTree(data, 2 * index + 1) # [1, 3, 7, 15, ...]
        pNode.right = creatBTree(data, 2 * index + 2) # [2, 5, 12, 25, ...]
    return pNode

Say you are cracking pathSum, populate the tree by calling

lst = [5,4,8,11,None,13,4,7,2,None,None,None,1]
root = creatBTree(lst, 0)

Thank you for the createBtree function code, Can you please clarify what the "index" parameter is for? — MMEL, Jan 26 '22 at 00:46

score 0 · Answer 3 · answered Jul 12 '22 at 13:21

Here is just beautified StefanPochmann's solution which was described at LeetCode's Help Center

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return 'TreeNode({})'.format(self.val)


def deserialize(string):
    if string == '[]':
        return None
    nodes = [None if val == 'null' else TreeNode(int(val))
             for val in string.strip('[]').split(',')]
    kids = nodes[::-1]
    root = kids.pop()
    for node in nodes:
        if node:
            if kids:
                node.left = kids.pop()
            if kids:
                node.right = kids.pop()
    return root


if __name__ == '__main__':
    tree = deserialize('[3,9,20,null,null,15,7]')
    assert tree == TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))

score 0 · Answer 4 · answered Feb 18 '23 at 20:32

Here's a drop-in replacement for the incomplete class LeetCode provides in questions such as https://leetcode.com/problems/invert-binary-tree/

import json

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        # Shrink the long json string by removing unnecessary lines
        t = '\n'.join([l for l in self.json_repr.split('\n')
            if '[' not in l and ']' not in l])
        return t.replace(',','')

    @property
    def json_repr(self):
        if self.val is None:
            return 'None'
        # Recursively construct a json-compliant representation
        if self.left is None:
            text = f"[{self.val}]"
        else:
            text = f"[{self.val}, [{self.left.json_repr}, {self.right.json_repr}]]"
        return json.dumps(json.loads(text), indent=1)

    def from_list(l):
        nodes = [TreeNode(v) for v in l]
        kids = nodes[::-1]
        root = kids.pop()
        for node in nodes:
            if node:
                if kids:
                    node.left = kids.pop()
                if kids:
                    node.right = kids.pop()
        return root

t = TreeNode.from_list([4,2,7,1,3,6,9])
print(t)

Returns:

How do I make TreeNode from list by Python

4 Answers4