使用递归以三个作为参数在二叉树中找到到叶节点的最长路径

Question

我正在自学准备考试，由于缺少示例和答案，运行遇到了一道题。练习说明如下：

"Write an algorithm that uses recursion to calculate the height of a given binary tree, ie. the longest existing path from the root node to a leaf node."

给出了方法的原始开始，必须修改此方法才能形成最终答案。此方法之外不允许使用其他方法：

// Binary tree height, find the longest path to a leaf node
public static int height(BTree t) {
    return 0;
}

在每次调用该函数之前，都会在树中添加一个节点。最终给定的树如下所示：

       10        
    __/  \__     
   5        15   
  / \      /  \  
 3   8   12    18
  \      /\      
   4    11 13

以下是我到目前为止的内容，但无法正常工作：

// Binary tree height, find the longest path to a leaf node
public static int height(BTree t) {

    BTreeNode n = t.getRoot();

    int height = 0;
    int calc = 0;

    if (n == null)
    {
        return height;
    }
    else
    {
        while (n!=null) {
            n = n.getLeftChild();
            calc++;
        }
    }

    if(calc > height) {
        height = calc-1;
        height = 0;
    }

    n = t.getRoot();
    while (n!=null) {
        n = n.getRightChild();
        calc++;
    }

    if(calc > height) {
        height = calc-1;
        height = 0;
    }


    return height;
}  // height()

请帮助我学习并通过考试，非常感谢所有帮助！

Answer 1

public int height(BTree t) {

     if(t == null) {
          return 0;
     }

     return 1 + Math.max(height(t.left), height(t.right));
}

Answer 2

在这种情况下，递归会是一个不错的选择。要获得高度，您从根节点和深度 0 开始。您有一个函数来获得最大深度。如果传递给它的节点为空（树的末尾），则此函数只是 returns 深度。否则它调用自己的深度增加1（还有另一层，因此深度必须增加）左右child。然后它 returns 找到了更高的深度。代码看起来像这样：

public static int getMaxDepth(BTreeNode node, int depth) {
    if (node == null) return depth;
    return Math.max(getMaxDepth(node.getLeftChild(), depth + 1), getMaxDepth(node.getRightChild(), depth + 1));
}

这将遍历整棵树并找到最长的路径。（我没有测试这段代码，但它应该可以工作。）

如果你想使用一个简单的 if 子句，你可以避免 Math.max()，它检查哪个深度更大，但我个人更喜欢这种方式。

你也可以尝试解决递归，用迭代代替。但随后您将不得不编写更多代码，这些代码将更难阅读和理解。没有递归的一种方法是跟踪当前层中的所有节点（及其深度）（例如使用 ArrayList），然后获取最后一层中节点的所有 children。之后，您使用找到的 children 更新列表并增加深度。如果 children 的列表是空的，那么你已经到达了树的末端并且可以达到 return 的深度。执行此操作的代码如下所示（同样未经测试）：

public static int getMaxDepth(BTreeNode root) {
    if (root == null) return 0;
    List<BTreeNode> currentLayer = new ArrayList<>();
    List<BTreeNode> children = new ArrayList<>();
    int depth = 0;

    currentLayer.add(root);
    while (0 < currentLayer.size()) {
        depth++;

        children.clear();
        for (BTreeNode node : currentLayer) {
            BTreeNode left = node.getLeftChild();
            if (left != null) children.add(left);

            BTreeNode right = node.getRightChild();
            if (right != null) children.add(right);
        }

        currentLayer.clear();
        currentLayer.addAll(children);
    }

    return depth;
}

使用递归以三个作为参数在二叉树中找到到叶节点的最长路径

Use recursion to find longest path to leaf node inside binary tree with the three as a parameter

java

algorithm

height

binary-tree