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

How do I make TreeNode from list by Python

2 Answers2