我如何从左边和右边的最远节点获取值

Question

我必须找到一个值和 bst 的远节点之间的距离。我已经做了一个可以找到两者之间距离的方法，但是我如何才能在节点内选择一个值？

  public int diameter(Node root)
   {
       // base case if tree is empty
       if (root == null)
           return 0;

       // get the height of left and right sub-trees
       int lheight = height(root.left);
       int rheight = height(root.right);

       // get the diameter of left and right sub-trees
       int ldiameter = diameter(root.left);
       int rdiameter = diameter(root.right);

       /* Return max of following three
         1) Diameter of left subtree
         2) Diameter of right subtree
         3) Height of left subtree + height of right subtree + 1
        */
       return Math.max(lheight + rheight + 1,
               Math.max(ldiameter, rdiameter));
   }

Answer 1

您应该提供对最远节点的引用；按照它的写法，函数只有 return 距离。请注意，我没有编译代码片段，因此可能需要调整，但只是为了说明一下：

    class HeightResult {
        int value;
        Node node;
    }
    
    class DiameterResult {
        int value;
        Node left;
        Node right;

        DiameterResult(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    
    public DiameterResult diameter(Node root) {
       // base case if tree is empty
       if (root == null)
           return 0;

       // get the height of left and right sub-trees
       HeightResult lheight = height(root.left);
       HeightResult rheight = height(root.right);

       // get the diameter of left and right sub-trees
       DiameterResult ldiameter = diameter(root.left);
       DiameterResult rdiameter = diameter(root.right);

       /* Return max of following three
         1) Diameter of left subtree
         2) Diameter of right subtree
         3) Height of left subtree + height of right subtree + 1
        */
       
         if (lheight.value + rheight.value + 1 >= Math.max(ldiameter.value, rdiameter.value)) {
            return new DiameterResult(lheight.value + rheight.value + 1, lheight.node, rheight.node);
         } else if (ldiameter.value >= rdiameter.value) {
            return ldiameter
         } else {
            return rdiameter;
         }
       }
   }

我如何从左边和右边的最远节点获取值

How I get a value from the furthest node from left and right

java

binary-search-tree