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

-2

我想计算一个二叉树的直径，为此我创建了一个getDiameter（）函数。现在在这个函数中，我需要调用Binary Tree的findHeight（）函数，它返回二叉树的高度。在代码1和代码2中计算高度的2个函数在概念上略有不同。在代码1我正在考虑单节点（只有根）的树的高度是1，在代码2中，我考虑单节点树的高度是0.所以在代码1的基本情况下，我返回0和code2我已经返回-1。我很困惑，其代码是正确的使用CODE1或代码2，因为直径的答案将会变化....递归使用树的高度的二叉树的直径？

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)); 
    } 

}

来源

2016-04-15 Aditya kumar

两者的概念在代码1和代码2是正确找到的高度二叉树。

问题是您必须与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)); 

}

现在直径的两个答案案件将是正确的.....

来源

2016-04-19 07:18:05

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

回答

相关问题