在二叉树中查找两个节点之间的距离

Question

网上许多关于"在二叉树中查找最小共同祖先"及其补充问题"查找 2 个节点之间的距离"的答案有 4 个问题：

1. 不考虑重复项
2. 不考虑输入节点是否无效/不存在/不在树中
3. 使用额外/辅助存储
4. 尽管获得了答案，但不截断遍历。

我编写了此示例以克服所有障碍。 但是由于我没有在这个方向上找到"单一"答案，如果我的代码有一个我缺少的显着缺点，我将不胜感激。也许没有。额外的眼球赞赏。

  public int distance(int n1, int n2) {        
        LCAData lcaData = new LCAData(null, 0, 0);
        int distance = foundDistance (root, lcaData, n1,  n2, new HashSet<Integer>());
        if (lcaData.lca != null) {
            return distance;
        } else {
            throw new IllegalArgumentException("The tree does not contain either one or more of input data. ");
        }
    }
  private static class LCAData {
        TreeNode lca;
        int count;
        public LCAData(TreeNode parent, int count) {
            this.lca = parent;
            this.count = count;
        }
    }
 private int foundDistance (TreeNode node, LCAData lcaData, int n1, int n2, Set<Integer> set) {
        assert set != null;
        if (node == null) {
            return 0;
        }
        // when both were found
        if (lcaData.count == 2) {
            return 0;
        }
        // when only one of them is found
        if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
            // second element to be found is not a duplicate node of the tree.
            if (!set.contains(node.item)) {
                lcaData.count++;
                return 1;
            }
        }
        int foundInCurrent = 0;  
        // when nothing was found (count == 0), or a duplicate tree node was found (count == 1)
        if (node.item == n1 || node.item == n2) {
            if (!set.contains(node.item)) {
                set.add(node.item);
                lcaData.count++;
            }
            // replace the old found node with new found node, in case of duplicate. this makes distance the shortest.
            foundInCurrent = 1;
        }
        int foundInLeft = foundDistance(node.left, lcaData, n1, n2, set);
        int foundInRight = foundDistance(node.right, lcaData, n1, n2, set);
        // second node was child of current, or both nodes were children of current
        if (((foundInLeft > 0 && foundInRight > 0) || 
                (foundInCurrent == 1 && foundInRight > 0) || 
                    (foundInCurrent == 1 && foundInLeft > 0)) &&
                        lcaData.lca == null) {
            // least common ancestor has been obtained
            lcaData.lca = node;
            return foundInLeft + foundInRight; 
        }
        // first node to match is the current node. none of its children are part of second node.
        if (foundInCurrent == 1) {
            return foundInCurrent;
        }
        // ancestor has been obtained, aka distance has been found. simply return the distance obtained
        if (lcaData.lca != null) {
            return foundInLeft + foundInRight;
        } 
        // one of the children of current node was a possible match.
        return (foundInLeft + foundInRight) > 0 ? (foundInLeft + foundInRight) + 1 : (foundInLeft + foundInRight);
    }

Answer 1

算法似乎是（没有完全将其分开）详尽地遍历整个树，直到找到一个节点，其中左侧有一个节点，右侧找到一个节点。 并随时创建一个额外的集合。

这里的问题似乎是你的算法效率非常低。 这可能符合您的要求，如果几乎从未执行过此特定操作。 但通常情况下你可以做得更好。