logo标签列表

寻找二叉树的直径

javatreebinary-tree
5
我将尝试在Java中找到二叉树的直径（树中任意两个节点之间包含最多节点的路径长度）。以下是我的代码片段：
public int diametre(Node node, int d)
{
    if(node==null)
        return 0;

    lh=diametre(node.left, d);
    rh=diametre(node.right, d);

    if(lh+rh+1>d)
        d=lh+rh+1;

    return findMax(lh, rh)+1;
}

在主方法中：
 System.out.println( bst.diametre(root,0) );

逻辑： 实际上是后序逻辑。变量“d”指的是子树（在该迭代中）的直径。当发现更大的值时，它将被更新。 “lh”表示：左子树的高度。 “rh”表示：右子树的高度。
但是它输出了错误的结果。
考虑的树：
   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9

空闲输出：5

但是这段代码却输出了3。

有人能找出问题所在吗...

1
你应该进行一些调试来找出你的代码行为与你预期的不符的地方。 - Oliver Charlesworth
1
首先，考虑算法。在你的代码中，d代表什么并不清楚。注意到对它的赋值没有效果，因为后面没有使用它。 - Eyal Schneider
这实际上是后序逻辑。d指的是子树的直径（在该迭代中）。如果发现更大的值，它将被更新。 - loknath
1
@loknath：但是更新不会在任何地方被注意到。Java始终按值传递参数。 - Eyal Schneider
如果您使用一个类实例变量，那应该没问题。另外，您应该打印出d而不是返回值。 - dsfdf
7个回答
10
public int diameter (Node root)
{
    if (root == null) return 0;
    else return Math.max (
        diameter (root.left), 
        Math.max (
            diameter (root.right),
            height (root.left) + height (root.right) + 1));
}

public int height (Node root)
{
    if (root == null) return 0;
    else return 1 + Math.max (height (root.left), height (root.right));
}
1
最后一行应该写成 root.left 而不是 root.length。 - Tony Wickham
2
我认为这个程序的运行时间是O(n*log(n))，因为你需要递归地遍历每个节点来计算直径，并且对于每个节点都要找到其高度（log(n)）。在计算直径时，你应该在遍历节点时同时获取其高度。 - Ajk_P
1
您可以通过从任何节点运行BFS，然后从最远的节点（第一个BFS期间访问的节点）运行另一个BFS来找到树的直径。 直径由第一个BFS中最后访问的节点和第二个BFS中最后访问的节点形成。 树是二叉树不会影响算法。
编辑：更改您编写的代码中d的值不会影响您传递的参数，因为在Java中原始类型不是按引用传递的。
我明白你的意思。如果这段代码是用C++编写的，并将变量d作为引用传递，它就能正常工作了。 - loknath
这个程序的运行时间是多少？我认为它是O(n)，其中n =节点数？ - Henley
@HenleyChiu 这是线性的 - 你运行两个BFS，每一个都与边数成线性关系（在树中，这与节点数的数量级相同）。 - Ivaylo Strandjev
1
我建议以下内容：
public static TreeAttr calcTreeDiameter(Node root) {
    if (root == null)
        return new TreeAttr(0, 0);

    TreeAttr leftAttr = calcTreeDiameter(root.getLeft());
    TreeAttr rightAttr = calcTreeDiameter(root.getRight());

    int maxDepth = Math.max(leftAttr.depth, rightAttr.depth);
    int maxDiam = Math.max(leftAttr.diameter, rightAttr.diameter);
    maxDiam = Math.max(maxDiam, leftAttr.depth + rightAttr.depth + 1);

    return new TreeAttr(maxDiam, maxDepth + 1);
}

TreeAttr是一个简单的结构体，包含子树的直径和深度。在递归中应该同时传入两个参数，因为最优解可能来自于某个子树，也可能来自于连接最长路径。

现在我看到我的解决方案与Mikhail Vladimirov的解决方案是等价的。 - Eyal Schneider
是的...它和Mikhail的代码都很直接。 - loknath
0

你应该使用树的高度来计算直径。创建一个getHeight()函数，它将以树的根节点作为参数并返回树的高度。利用这个值和递归的帮助，我们可以计算出树的直径。以下是代码...

计算直径的函数：

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

计算树高的函数：

public static int findHeight(BinaryTreeNode node) {
if(node == null)
    return 0;

else {
    return 1+Math.max(findHeight(node.left), findHeight(node.right));
}
}
0

算法的时间复杂度为O(n)。同时计算高度和路径。

public static int findLongestPath(TreeNode root)
{
  // longest path = max (h1 + h2 + 2, longestpath(left), longestpath(right);

  int[] treeInfo = longestPathHelper(root);

  return treeInfo[0];
}

private static int[] longestPathHelper(TreeNode root)
{
  int[] retVal = new int[2];

  if (root == null)
  {
     //height and longest path are 0
     retVal[0] = 0;
     retVal[1] = 0;
  }

  int[] leftInfo = longestPathHelper(root.getLeft());
  int[] rightInfo = longestPathHelper(root.getRight());

  retVal[0] = Math.max(leftInfo[1] + rightInfo[1] + 2, Math.max(leftInfo[0], rightInfo[0]));
  retVal[1] = Math.max(leftInfo[1], rightInfo[1]) + 1;

  return retVal;
}
0
int max=0;
public int diameter(Tree root) {
  if(root==null) return 0;
  int l=diameter(root.left);
  int r=diameter(root.right);
  max=Math.max(max,l+r+1);
  return l>r:l+1:r+1;
}

max是最大直径。

这个解决方案存在问题。例如，对于具有两个叶子节点的根，它返回了一个不正确的结果（2）。此外，请注意max变量未被使用。 - Eyal Schneider
@EyalSchneider 最终结果应该将max返回为最大直径，而不是此函数的返回值。 - dsfdf
我明白了。所以你实际上有一个带有副作用存储在max中的深度函数。我会更改函数名称... - Eyal Schneider
0

二叉树的直径在O(n)时间复杂度内，它将跟踪通过根节点或不通过根节点的直径，并使用相同的高度函数来跟踪直径。

DiameterOfTree.class

import BinaryTree.BinaryTreeNode;

public class DiameterOfBinaryTree {
    private int DIAMETER = 0;

    public void getDiameterOfBinaryTree(BinaryTreeNode node) {
        getHeightUtil(node, DIAMETER);
        System.out.print("\n\n Maximum Diameter of the tree is : " + DIAMETER);
    }

    private int getHeightUtil(BinaryTreeNode node, Integer maXValue) {
        if (node == null) {
            return 0;
        }

        // Here we get the maximum value returned + 1 for each subtree left or 
        //  right 
        int leftHeight = getHeightUtil(node.getLeft(), maXValue); 
        int rightHeight = getHeightUtil(node.getRight(), maXValue);

        //finding the new diameter at a particular node and adding 1 to 
        //include that particular node as well: leftHeight + rightHeight + 1 
        DIAMETER = Math.max(DIAMETER, leftHeight + rightHeight + 1);

        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Main.java

package BinaryTree;

public class Main {

    public static void main(String[] args) {
        //Initialise root
        BinaryTreeNode root = new BinaryTreeNode(40);

        //Create a binary Tree
        InitialiseBinaryTree initialiseBinaryTree = new InitialiseBinaryTree();
        initialiseBinaryTree.initialise(root);

        // Find the diameter of the binary tree 
        new DiameterOfBinaryTree().getDiameterOfBinaryTree(root);
    }

}

InitialiseBinaryTree.java

package BinaryTree;

class InitialiseBinaryTree {
    void initialise(BinaryTreeNode root) {
        BinaryTreeOperation bto = new BinaryTreeOperation();
        int[] data = {20, 50, 10, 30, 5,8, 25, 32, 33};
        for (int aData : data) {
            bto.insertElementInBinaryTree(root, aData);
        }
    }
}

BinaryTreeOperation.java

package BinaryTree;

class BinaryTreeOperation {
    private boolean findInBinaryTree(BinaryTreeNode node, int data) {
        return node != null &&
                (data == node.getData() || (findInBinaryTree(node.getLeft(), data) || findInBinaryTree(node.getRight(), data)));
    }

    void insertElementInBinaryTree(BinaryTreeNode node, int data) {
        if (node == null) {
            new BinaryTreeNode(data);
        } else {
            insertHelper(node, data);
        }
    }

    private void insertHelper(BinaryTreeNode node, int data) {
        if (node.getData() > data) {
            if (node.getLeft() == null) {
                node.setLeft(new BinaryTreeNode(data));
            } else {
                insertHelper(node.getLeft(), data);
            }
        } else {
            if (node.getRight() == null) {
                node.setRight(new BinaryTreeNode(data));
            } else {
                insertHelper(node.getRight(), data);
            }
        }
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接