java—如何从左、右最远的节点获取值

4dbbbstv  于 2021-06-30  发布在  Java
关注(0)|答案(1)|浏览(274)

我必须找到一个值和一个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));
   }
jdgnovmf

jdgnovmf1#

您应该提供对最远节点的引用;按照编写的方式,函数只返回距离。请注意,我没有编译代码片段,因此它可能需要进行调整,但只是给出一个想法:

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

相关问题