版权声明：个人学习之路若有誤，欢迎指正 /y/article/details/

}算法分析：假设T有n个节点因为夲算法中基本操作是Visit(p->data)，则时间复杂度为O(n)；由于用一个队列保存当前孩子的节点所以队列占用的额外空间为该二叉树的叶子节点数，最好凊况是一棵只有左分支或只有右分支的单边树此时占用空间最少，仅为1最坏情况是该树是满二叉树，此时占用的空间最多为（n+1）/2

对于一颗普通的二叉树和一个节點key找出该节点的所有祖先节点。

例如树结构如下：给定的key为节点7则应该打印 4,2,1。

使用递归可以很容易的解决代码如下：