有没有更简洁的方法来找到满足条件的树中的顶部节点

Question

对于树中的给定节点，我试图找到其最高祖先（或节点本身），但不跨越树中的某个 "barrier"（特定节点类型）- 如果有这么一个"barrier"节点。如果没有 "barrier" 节点，我想 return 树中的顶部节点。

听起来比实际更复杂 - 这是一些代码：

    public Node GetHighestRelevantAncestorOrSelf(Node node)
    {
        Node topNode = node;
        bool newTopNodeFound;
        do
        {
            Node newTopNode = GetParent(topNode);

            newTopNodeFound = (newTopNode != null && !IsBarrierNode(newTopNode));

            if (newTopNodeFound)
            {
                topNode = newTopNode;
            }
        } while (newTopNodeFound);

        return topNode;
    }

有没有更好的写法，即不用计算 "newTopNodeFound" 两次？也许使用 for 循环？

Answer 1

完全摆脱它。

public Node GetHighestRelevantAncestorOrSelf(Node node)
{
    Node topNode = null;
    while(node != null && !IsBarrierNode(node))
        node = GetParent(topNode = node);
    return topNode;
}

尽管这与您拥有的功能在功能上略有不同。如果你传入的 node 是一个屏障节点，那么你将 returning 该节点，而这将是 return null。如果您想更改它，请将行 Node topNode = null; 修改为 Node topNode = node;

Answer 2

你可以使用递归

public Node GetTopNode(Node node)
{
    var parent = GetParent(node);
    return (parent != null && !IsBarrierNode(parent))
        ? GetTopNode(parent)
        : node;
}

Answer 3

在不修改原始节点的情况下执行此操作的一种方法是创建一个引用它的新变量，然后 "increment" 在 while(true) 循环中将此变量设置为父节点，如果有效：

public Node GetHighestRelevantAncestorOrSelf(Node node)
{
    Node result = node;

    while (true)
    {
        Node parent = GetParent(result);
        if (parent == null || IsBarrierNode(parent)) return result; // This exits the loop
        result = parent;
    }
}

有没有更简洁的方法来找到满足条件的树中的顶部节点

Is there a more concise way to find the top node in a tree that meets a criterion

c#

tree

traversal

tree-traversal