二叉树的分层遍历

今天去面试的时候被问到二叉树的分层遍历，因为原来写Python脚本的时候自己用队列的方法写过一次分层遍历。结果面试官说能不能用递归的方法，不用队列实现。唔，临时想没有想起来，因此记录一下。

首先定义一个二叉树的节点：

class TreeNode:
    def __init__(self,value):
        self.value=value
        self.left=None
        self.right=None

遍历算法为：

def traverse(node):
    '''''将要遍历的根节点放入队列中，并放入一个结束的标志位'''
    if node is None:
        return
    q=Queue.Queue()
    q.put(node)
    q.put(Sign())
    traverse_re(q)

def traverse_re(queue):
    node=queue.get()
    if node is None or isinstance(node, Sign):
        return
    while(not isinstance(node, Sign)):
        print node.value,
        #将左右子树放入队列中
        if node.left is not None:
            queue.put(node.left)
        if node.right is not None:
            queue.put(node.right)
        node=queue.get()
    print ''
    queue.put(Sign())
    traverse_re(queue)

验证方法为：

if __name__=="__main__":
    root=TreeNode(1)
    left=TreeNode(2)
    right=TreeNode(3)
    root.left,root.right=left,right
    left.left=TreeNode(4)
    right.left,right.right=TreeNode(6),TreeNode(7)
    traverse(root)

之后在《编程之美》上看到了不使用队列的递归遍历方法：

def nodeAtLevel(node, level):
    if node is None or level <0:
        return 0
    if level==0:
        print node.value,
        return 1
    return nodeAtLevel(node.left, level-1)+nodeAtLevel(node.right, level-1)

def nodeByLevel(root):
    level=0
    while(True):
        if(nodeAtLevel(root, level)==0):
            break
        level+=1
        print ""

不过还是使用队列遍历的效率高，时间复杂度低