二叉链表输出每个结点到根结点路径上所有结点值

Question

如题，我不知道是用先序还是后序遍历比较好，也不知道要怎么找每个结点的父结点，是另外写一个函数，还是直接在遍历的过程中访问父结点，感觉好绕啊！

Answer 1

因为只知道叶结点，所以只能通过判断某一结点的左右子结点是否是所求的叶结点得到，即只有先知道子结点，才能知道父结点。在后序遍历中，子结点比父结点先出栈。我们用一个变量a记录子结点（a一开始被赋值为所求叶结点），当进行弹栈时，要同时判断被弹结点的子结点，如果与a相同，则将该被弹结点赋值给a，递归进行，知道根结点。