使用 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)

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

参考完整的运行示例 from 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)

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

Adding values to missing nodes in binary tree using Python

binary-tree

python-2.7