如何在二叉树中找到距离给定节点 k 的节点

Question

我遇到了 THIS geeksforgeeks post 在二叉树中找到距离给定节点 k 的节点。

即使花了几个小时我也无法理解它。特别是在祖先中找到距离 k 处的节点的部分。

有人可以帮我在 geeksforgeeks post 的 code/algorithm 上做一个小试运行吗？或者任何其他不使用父指针的易于理解的解决方案？

Answer 1

假设目标节点的深度是D。

1. 如果你想要的节点在以目标节点为根的子树中，它们的深度应该是D+k。
2. 之后，您需要找到目标节点的所有祖先。 对于每一个祖先，如果深度为d，那么这个祖先到目标节点的距离就是D-d。 所以最后一步就是在这个祖先的其他子树中找到距离为k - (D-d)的节点。