二叉树中的交替级别顺序遍历

Question

我正在尝试对二叉树进行层序遍历。但是诀窍不是正常的级别顺序遍历，我想交替进行。例如

普通级别顺序遍历：1 2 3 4 5

我正在寻找的是假设我们打印根。现在对于每个偶数级别，我想逆时针旋转，对于每个奇数级别，我想顺时针旋转：

对于这种遍历，输出应该是：1 2 3 4 5

这是我迄今为止尝试过的方法，但这产生的输出与我试图实现的输出略有不同：

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


    # Function to  print level order traversal of tree
    def printLevelOrder(root):
        h = height(root)
        for i in range(1, h+1):     
           printGivenLevel(root, i)

    def printGivenLevel(root , level):
        if root is None:
           return
        if level == 1:
           print(root.val)
        elif level > 1 and level%2 == 0:
             #print("level",level)
             printGivenLevel(root.right , level-1)
             printGivenLevel(root.left , level-1)

        else:
           #print("level",level)
            printGivenLevel(root.left, level-1)
            printGivenLevel(root.right , level-1)


    def height(node):
        if node is None:
           return 0
        else :
        # Compute the height of each subtree 
           lheight = height(node.left)
           rheight = height(node.right)

           #Use the larger one
           if lheight > rheight :
              return lheight+1
           else:
              return rheight+1

# Driver code
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.right  = Node(7)
root.left.left.left  = Node(8)
root.left.left.right  = Node(9)
root.right.left.left  = Node(10)
root.right.right.right  = Node(11)


print ("Level order traversal of binary tree is -")
printLevelOrder(root)

这个程序产生这个输出：

1 3 2 5 4 7 6 10 11 9 8

我需要的：

1 2 3 7 6 5 4 8 9 10 11.

Answer 1

像这样更改函数 printGivenLevel()

def printGivenLevel(root , levelrem, level):                                    
    if root is None:                                                            
       return                                                                   
    if levelrem == 1:                                                           
       print(root.val)                                                          
    elif level > 1 and level%2 == 0:                                            
         printGivenLevel(root.left , levelrem-1, level)    # you had root.right                      
         printGivenLevel(root.right , levelrem-1, level)   # you had root.left                       

    else:                                                                       
        printGivenLevel(root.right, levelrem-1, level)     # you had root.left                    
        printGivenLevel(root.left , levelrem-1, level)     # you had root.right

这里的levelrem变量表示何时打印一片叶子，level表示叶子的实际层级。将 printGivenLevel() 调用为 printGivenLevel(root, i, i)

另请注意 缩进在 python 中非常重要。您在问题中提供的代码无法按原样工作。必须了解 class 节点只有 init() 方法。

二叉树中的交替级别顺序遍历

Alternate Level order traversal in binary tree

python

binary-tree

data-structures