c# - 二叉树单向最大高度的解决方法

Question

我遇到了一个问题，我试图解决这个问题。该问题需要找到二叉树在一个方向 的最大高度。例如。如果分支继续向左，则高度继续增加，但如果分支随后向右，高度将重置为 1。

我在 C# 中想出了以下内容，我什至不确定它是否正确。

有人知道最优解吗？

 class MaxHeightInOneDirection
{
    public void Run()
    {
        Tree a = new Tree();
        a.x= 20;

        Tree b = new Tree();
        b.x = 21;

        Tree c = new Tree();
        c.x = 12;
        c.l = b;
        c.r = a;

        Tree d = new Tree();
        d.x = 10;
        d.l = c;

        Tree e = new Tree();
        e.x = 3;

        Tree f = new Tree();
        f.x = 5;
        f.l = e;
        f.r = d;

        int maxHeight = GetHeight(f)[2];

    }

    public int[] GetHeight(Tree root)
    {
        if (root == null)
            return new int[]{-1,-1, 0};

        int[] leftResult = GetHeight(root.l);
        int[] rightResult = GetHeight(root.r);

        // Increase left on current left
        leftResult[0]++;
        // Set right result on current left to 0
        leftResult[1] = 0;
        // Set left result on current right to 0
        rightResult[0] = 0;
        // Increase right on current right
        rightResult[1]++;

        int leftMaxSoFar = leftResult[2];
        int rightMaxSoFar = rightResult[2];

        int maxValueSoFar = Math.Max(leftMaxSoFar, leftResult[0]);
        maxValueSoFar = Math.Max(maxValueSoFar, rightResult[1]);
        maxValueSoFar = Math.Max(maxValueSoFar, rightMaxSoFar);

        return new int[] { leftResult[0], rightResult[1], maxValueSoFar };
    }
}

Answer 1

要找到树的高度，您可以简单地使用这个算法:- here

在 C# 中做一些事情

int MaxDepth(Tree node) 
{
   if (node==NULL) 
       return 0;
   else
   {      
       int lDepth = maxDepth(node->left);
       int rDepth = maxDepth(node->right);

       /* use the larger one */
       if (lDepth > rDepth) 
           return(lDepth+1);
       else return(rDepth+1);
   }
}