在特殊二叉树中查找最少步数

引言

二叉树是计算机科学和编程中常用的基本数据结构。一种常见的特殊二叉树是每条边都有一个指向其父节点的额外指针的二叉树。带有父节点指针的二叉树，即特殊二叉树，是一种每个节点都链接到其父节点的树数据结构。通过额外指向父节点的指针，可以轻松导航，这在许多方法和场景中都非常有用。

特殊二叉树节点的结构

算法

• 通过父节点指针向上遍历树，确定每个节点的深度。
• 从较深的节点向上遍历树，直到两个节点都处于同一深度。
• 从每个节点向上遍历，直到找到共同的祖先。
• 到达共同祖先后剩余的总深度就是最小步数。

代码

输出

代码解释

节点结构

• Node 结构定义了二叉树节点的根本结构。
• 每个节点都有一个整数值，指向其父节点（parent）的指针，以及指向其左子节点和右子节点的指针。

findDepth 函数

• findDepth 函数通过遍历特定节点父节点的父节点指针，确定该节点在特殊二叉树中的深度。
• 在父节点引用为 NULL 之前，每次迭代将深度加一，并将深度变量初始化为 0。
• 最终的深度值被返回。

findMinimumSteps 函数

• findMinimumSteps 函数计算从一个节点到另一个节点所需的最小步数，给定两个输入节点，节点 1 和节点 2。
• 为了找到两个节点的深度，它利用了 findDepth 函数。
• 然后，该函数遍历树并修改节点，使它们达到相同的深度。
• 它会一直进行，直到找到一个共同的祖先。
• 最后，它通过累加所有剩余的深度来确定所需的最小步数。

主函数

• 为了测试目的，main 函数中构建了一个示例特殊二叉树。
• 使用 malloc 为节点分配内存。
• 使用示例数据设置树结构，并正确分配父节点指针。
• 将两个节点（节点 1 和节点 2）传递给 findMinimumSteps 函数，并报告输出。

内存清理

• 为了防止内存泄漏并释放动态分配的内存，代码包含了内存清理的 free 操作。
• 从叶子节点开始，向根节点遍历，按照创建的相反顺序释放每个分配的节点。

时间和空间复杂度

`findDepth` 和 `findMinimumSteps` 函数是影响代码时间复杂度的主要因素。 `findDepth` 方法由于需要从特定节点遍历到根节点，因此时间复杂度为 O(h)，其中 h 是树的高度。类似地，`findMinimumSteps` 函数由于搜索直到找到共同祖先，因此时间复杂度也为 O(h)。当树变得更平衡时，时间复杂度通常很高效，对于 n 个节点，h 接近 log(n)。由于常量内存使用，不随输入大小而增加，因此空间复杂度为 O(1)。