Unicorns OA 面试真题解析：二叉树中两节点的距离（Find the Distance Between Two Nodes in a Binary Tree）

Find the distance between two nodes in a binary tree. The distance between two nodes is defined as the minimum number of edges to be traversed to reach one node from another.

Example:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7
          \
           8

Dist(4, 5) = 2
Dist(4, 6) = 4
Dist(4, 3) = 3
Dist(4, 8) = 5

这道题要求在二叉树中计算两个节点之间的最短边数，本质上就是求两点在树上的距离。标准做法通常是先找到两个节点的最近公共祖先（LCA），再分别计算两个节点到 LCA 的深度之和；也可以用 DFS 先定位目标节点并在回溯过程中统计路径长度。示例中，4 和 5 的距离是 2，因为它们都在节点 2 的子树下；4 和 6 的距离会经过 2、1、3，因此是 4。