Hi dear every one, I wonder why my solution is wrong. Thanks!


  • 0
    L
        public int diameterOfBinaryTree(TreeNode root) {
            if(root == null) return 0;
            return longestPath(root.left)+longestPath(root.right);
        }
        
        public int longestPath(TreeNode root)
        {
            if(root==null) return 0;
            
            return 1+Math.max(longestPath(root.left), longestPath(root.right));
        }
    }```

  • 0
    L

    @larrylearnquickplz I have the same blocking case here: [4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]. I am wondering why the expected result is 8 too


  • 0
    S

    I know this question is old, but I'll answer it.

    This solution is wrong because it returns the max depth of the left, and the right, respective from the root only.

    What about if our solution lies elsewhere?

                           a
                          / \
                         c   b
                        / \
                       e   f
                      / \ / \
                     g  h i  j
                    /         \
                   k           l
    

    If we only did the max of the left + right, we'd get 4 + 1, so 5, but it's pretty clear the bigger route is down on the left side, through 'c'.

    Basically at each node we have 2 actions. We need to look at both branches combined to see how they compare to the overall max thus far, and we need to contribute a left or right side, whichever is more, so the other nodes higher up in the tree can attempt to do the same calculation of the sum of their branches against the current max.

    Another thing to note is we cannot return the value of both of a nodes branches (left + right), because then it might get calculated into another node's calculation of both of it's branches. We'd end up with forked routes which are invalid. That is the reasoning for most of these solutions hoisting a max value our of their functions.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.