python-2.7 - 使用Python向二叉树中的缺失节点添加值

Question

我有以下二叉树：

..............1
............/....\
...........2......3
........../..\......\
.........4....5.....6
..........\........./
...........8.......7

我会通过将（-1）添加到丢失的节点并逐行获取来将其完成为完整的二叉树。这意味着树将如下所示：

..............1
............/.....\
...........2.........3
........../..\....../..\
.........4....5....-1.....6
......../.\.../\..../.\../.\
......-1...8.-1.-1.-1.-1.7.-1

所需的结果如下：

1
2 3
4 5 -1 6
-1 8 -1 -1 -1 -1 7 -1

创建二叉树的代码是：

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



root =  Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.left.left = Node(7)
root.left.left.right = Node(8)

标签： python-2.7binary-tree

Answer 1

唯一的事情是你必须确定第level一个并通过它。但是，这也可以处理。填充缺失的节点：

def fillMissingNodes(root, level):
    if (root == None):
        return
    if(root.left == None and level > 0):
        root.left = Node(-1)
    if(root.right == None and level > 0):
        root.right = Node(-1)
    fillMissingNodes(root.left, level - 1)
    fillMissingNodes(root.right, level - 1)

fillMissingNodes(root, 3)

现在，您可以以任何您想要的方式遍历。这是使用队列遍历的级别顺序：

def traverseLevelOrder(q):
    while(q.qsize() > 1):
        current = q.get()
        if(current == None):
            q.put(None)
            print("\n")
        else:
            if(current.left != None):
                q.put(current.left)
            if(current.right != None):
                q.put(current.right)
            print(current.val),

traverseLevelOrder(q)

如果您想在此处组合填充缺失节点和遍历线顺序，请执行以下操作：

def traverseLevelOrderAndFillMissingNodes(q, level):
    while(q.qsize() > 1):
        current = q.get()
        if(current == None):
            q.put(None)
            print("\n")
            level = level - 1
        else:
            if(current.left == None and level > 0):
                current.left = Node(-1)
            if(current.right == None and level > 0):
                current.right = Node(-1)
            if(current.left != None):
                q.put(current.left)
            if(current.right != None):
                q.put(current.right)
            print(current.val),


traverseLevelOrderAndFillMissingNodes(q, 3)

这是输出：

1 
2 3 
4 5 -1 6 
-1 8 -1 -1 -1 -1 7 -1

参考来自github的完整运行示例

顺便说一句，您的树创建代码与图中所示的并不完全相同。左右有一个小问题（寻找 6 和 7 加法）。这是正确的：

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
root.right.right.left = Node(7)
root.left.left.right = Node(8)