python构建二叉树测试用例--返回根节点

python构建二叉树测试用例–返回根节点

# 定义树节点.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
#将输入的列表转化为一棵二叉树，返回根节点
def deserialize(data):
    def dfs(data):
        val = data.pop(0)
        if val == null:
            return None

        node = TreeNode(val)
        node.left = dfs(data)
        node.right = dfs(data)
        return node
    return dfs(data)

# 中序遍历：
def inOrder(root):
    if not root:
        return []
    return  inOrder(root.left) +[root.val]+ inOrder(root.right)

# 前序遍历：
def preOrder(root):
    if not root:
        return []
    return [root.val] + preOrder(root.left) + preOrder(root.right)

构造如下二叉树

4
   /    
  2   	 7
 /    	 / 
1   3   5   8
#可认为最后还有有8个null叶子结点，在以下第二种方法中需要时使用

第一种：

#测试1：全部手动配置左右结点，比较繁琐
nodelist=[TreeNode(i)for i in [4,2,7,1,3,5,8]]
nodelist[0].left=nodelist[1]
nodelist[0].right=nodelist[2]
nodelist[1].left=nodelist[3]
nodelist[1].right=nodelist[4]
nodelist[2].left=nodelist[5]
nodelist[2].right=nodelist[6]
root = nodelist[0]
print(二叉树根节点为：,root)
print(前序遍历,preOrder(root))
print(前序遍历,inOrder(root))

二叉树根节点为： <main.TreeNode object at 0x000001EF18D21668> 前序遍历 [4, 2, 1, 3, 7, 5, 8] 前序遍历 [1, 2, 3, 4, 5, 7, 8]

第二种：

#测试2：调用以上deserialize函数，给定的列表需要包含所有的null的叶子结点
data = [4, 2, 1, null, null, 3, null,null, 7, 5, null, null, 8, null, null]
root = deserialize(data)
print(二叉树根节点为：,root)
print(前序遍历,preOrder(root))
print(前序遍历,inOrder(root))

输出： 二叉树根节点为： <main.TreeNode object at 0x000001EF18D21160> 前序遍历 [4, 2, 1, 3, 7, 5, 8] 前序遍历 [1, 2, 3, 4, 5, 7, 8]

第三种：

# 测试3：直接通过已有的树的结点来定义
root = TreeNode(4, TreeNode(2, TreeNode(1),TreeNode(3)),TreeNode(7,TreeNode(5),TreeNode(8)))
print(二叉树根节点为：,root)
print(前序遍历,preOrder(root))
print(前序遍历,inOrder(root))

输出： 二叉树根节点为： <main.TreeNode object at 0x000001EF18D01B70> 前序遍历 [4, 2, 1, 3, 7, 5, 8] 前序遍历 [1, 2, 3, 4, 5, 7, 8]