0

鉴于这个代表一棵树的类,我对如何返回一个包含作为树高度一部分的节点的列表有点困惑。

public class TreeNode<T>
    {

        private T m_Data;
        public T Data
        {
            get
            {
                return m_Data;
            }
            set
            {
                m_Data = value;
            }
        }
        private readonly List<TreeNode<T>> m_Children;
        public List<TreeNode<T>> Children
        {
            get
            {
                return m_Children;
            }
        }

        public TreeNode(T i_Data)
        {
            this.m_Data = i_Data;
            m_Children = new List<TreeNode<T>>();
        }

        public void AddChild(T data)
        {
            m_Children.Add(new TreeNode<T>(data));
           // return m_Children[m_Children.Count-1];
        }

        public List<T> LongestPathNodes(TreeNode<T> i_node)//this function
        {
            if(i_node.m_Children.Count == 0)
            {
                List<T> choosenMove = new List<T>(1);
                choosenMove.Add(i_node.Data);
                return choosenMove;

            }
            else
            {
                foreach(TreeNode<T> treeNode in i_node.Children)
                {
                    
                }
            }
        }

我正在谈论的函数是“LongestPathNodes”函数,我认为它必须是递归的,我写了其中的一部分,但我对如何进行感到困惑,因为树不必是一个二进制的。

4

1 回答 1

1

定义一个Height属性:

public int Height =>
    m_Children != null && m_Children.Any()
    ? m_Children.Max(x => x.Height) + 1
    : 1;

现在您可以从任何给定节点返回最长分支的节点:

public IEnumerable<TreeNode<T>> LongestPathNodes()
{
    yield return this;
    var children = m_Children?
        .OrderByDescending(x => x.Height)
        .FirstOrDefault()?
        .LongestPathNodes();
    if (children != null)
    {
        foreach (var child in children) yield return child;
    }
}

如果您需要它,List<T>它是一个 LINQ 单线:

var list = node.LongestPathNodes().Select(x => x.m__Data).ToList();
于 2020-09-03T15:21:33.687 回答