在⼆叉树中有两个结点m和n，若m是n的祖先，则使⽤后序遍历
可以到从m到n的路径
可作此图：先序中序后序遍历二叉树
可见，此时m是n的祖先。
下⾯进⾏分析（圆球为输出）。
1. 若使⽤先序遍历，即“根左右”，此时动作是：
在n⼊栈前m已经出栈，⽆法确定路径。
2. 若使⽤中序遍历，即“左根右”，此时动作是：
在n⼊栈前m已经出栈，⽆法确定路径。
3. 若使⽤中序遍历，即“左根右”，此时动作是：
在n⼊栈后，m仍在栈中，且此时栈中有m、b、n，可见路径为m-b-n，路径到。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。