二叉树的直径减 1

Question

我不熟悉递归和树。我无法计算出二叉树的直径。我的解决方案差了 1，我不知道哪里出错了。我在这里查看了一个类似的问题：Finding Diameter of a Tree 但我无法理解它是否确实是同一个问题。下图的答案直径为 8（两个节点之间的最长路径）。但是我得到了 7。感谢任何帮助或建议。提前致谢。

可以在这里找到问题：https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3293/

106 个测试用例中我只失败了 4 个。

public class DiameterBinaryTree {

    public static void main(String argv[]){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(diameter(root));
    }

    public static int diameter(TreeNode root){
        int maxDiameter = Integer.MIN_VALUE;
        return diameterHelper(root, maxDiameter) ;
    }

    public static int diameterHelper(TreeNode root, int maxDiameter){
        if(root == null ) return 0;
        diameterHelper(root.left, maxDiameter);
        int leftHeight = findHeight(root.left);
        diameterHelper(root.right, maxDiameter);
        int rightHeight = findHeight(root.right);
        return Math.max(maxDiameter, leftHeight + rightHeight) ;
    }

    public static int findHeight(TreeNode root ){
        int countLeft = Integer.MIN_VALUE;
        int countRight = Integer.MIN_VALUE;
        return findHeightHelper(root, countLeft, countRight) ;
    }

    public static int findHeightHelper(TreeNode root, int countLeft, int countRight){
        if(root == null ) return 0;
        countLeft = 1 + findHeightHelper(root.left, countLeft, countRight);
        countRight = 1 + findHeightHelper(root.right, countLeft, countRight);
        return Math.max(countLeft, countRight) ;
    }
}

Answer 1

在比较当前直径之前，我没有考虑左最大直径和右最大直径。

return Math.max(Math.max(左直径, 右直径), 左高度 + 右高度);

二叉树的直径减 1

Diameter of Binary Tree Off by 1

java

algorithm

tree

binary-tree

graph