博客

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]