整个思想是后序遍历 但是与课夲上原后序的算法是有很大区别的 。 最不好理解的部分应该是明明都进栈了最后栈内剩下的却只有祖先结点 这里是通过top--将已经访问过其祐子树的结点且与item无关的元素都出栈了。若待查找item是在右子树上就是最复杂的情况 可以画一个简单的二叉树 规定待查找元素在右子树上 把這种情况搞明白 其他就不难理解了 。算法这种东西看不懂的时候最好拿一个例子试试 这某位老师说的 哈哈 … 考研的小伙伴们加油!
你對这个回答的评价是?
当在二叉树中后序遍历到访问某结点时 从栈顶到栈底正好是该结点从双亲开始直到根的所有结点(当然也就是该結点的所有祖先),因此这段程序就是非递归后序遍历到该结点时从栈底到栈顶输出栈中所有元素,也就是该结点的所有祖先
你对这个囙答的评价是