使用树的高度递归二叉树的直径？

Question

我想计算二叉树的直径，我已经为其创建了一个 getDiameter() 函数。现在在这个函数中我需要调用二叉树的 findHeight() 函数，它 returns 二叉树的高度。 code1 和 code2 中计算高度的 2 个函数在概念上没有什么不同。在代码 1 中，我考虑单节点（仅根）树的高度为 1，在代码 2 中，我考虑单节点树的高度为 0。因此，在代码 1 的基本情况下，我返回了 0，在代码 2 中我已经返回-1。我很困惑使用 code1 或 code2 哪个代码是正确的，因为直径的答案会有所不同....

public static int getDiameter(BinaryTreeNode root) {        
    if (root == null)
        return 0;

    int rootDiameter = findHeight(root.getLeft()) + findHeight(root.getRight()) + 1;
    int leftDiameter = getDiameter(root.getLeft());
    int rightDiameter = getDiameter(root.getRight());

    return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}


code1

public static int findHeight(BinaryTreeNode node) {
    if(node == null)
        return 0;
    else {
        return 1+Math.max(findHeight(node.left), findHeight(node.right));
    }

}
Code 2

public static int findHeight(BinaryTreeNode node) {
    if(node == null)
        return -1;
    else {
        return 1+Math.max(findHeight(node.left), findHeight(node.right));
    }

}

Answer 1

Both the concepts in code 1 and code 2 are correct to find the height of a binary tree.

关键是你必须与getDiameter() 2个不同代码的函数保持一致。

因此，如果使用代码 1，getDiameter() 函数将是：

public static int getDiameter(BinaryTreeNode root) {        

if (root == null)
    return 0;

int rootDiameter = findHeight(root.getLeft()) + findHeight(root.getRight()) + 1;
int leftDiameter = getDiameter(root.getLeft());
int rightDiameter = getDiameter(root.getRight());

return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));

}

如果使用代码 2，getDiameter() 函数将是：

public static int getDiameter(BinaryTreeNode root) {        
if (root == null)
    return 0;

int rootDiameter = findHeight(root.getLeft()) + findHeight(root.getRight()) + 3;
int leftDiameter = getDiameter(root.getLeft());
int rightDiameter = getDiameter(root.getRight());

return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));

}

现在两种情况下直径的答案都是正确的.....

使用树的高度递归二叉树的直径？

Diameter of binary tree recursively using the height of tree?

binary-tree

data-structures