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

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)

该程序产生以下输出:

< code>1 3 2 5 4 7 6 10 11 9 8

我需要什么：

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

Answer 1

像这样更改函数printGiven水准（）

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（）作为printGi文Level（root，i，i）

另外请注意，缩进在python中非常重要。你在问题中给出的代码不能按原样工作。你必须理解类Node只有init（）方法。