Java easy to understand solution


  • 8
    S
    public class Solution {
        public int diameterOfBinaryTree(TreeNode root) {
            if(root == null){
                return 0;
            }
           int dia = depth(root.left) + depth(root.right);
           int ldia = diameterOfBinaryTree(root.left);
           int rdia = diameterOfBinaryTree(root.right);
           return Math.max(dia,Math.max(ldia,rdia));
            
        }
        public int depth(TreeNode root){
            if(root == null){
                return 0;
            }
            return 1+Math.max(depth(root.left), depth(root.right));
        }
        
    }
    
    

  • 0
    1

    what is time complexity of your algorithm?


  • 12

    this solution is intuitive but the performance is not good because of the overlapping subproblems when calculate depth.

    diameterOfBinaryTree is called on every node. In each call, it traverses all descendants of that node to get the depth.

    • for root node, it is n => n + 1 - 2^0
    • for all nodes on 2nd level, it is 2 * (n - 1) / 2 => n - 1 => n + 1 - 2^1
    • for all nodes on 3rd level, it is 4 * (n - 3) / 4 => n - 3 => n + 1 - 2^2
    • for all nodes on 4th level, it is 8 * (n - 7) / 8 => n - 7 => n + 1 - 2^3
      ...
    • for all nodes on last level, it is n + 1 - 2^(h-1). h is max tree depth.

    Add them up, the result is (n+1) * h - (1 + 2 + 4 ... + 2^(h-1)). In worst case, the latter part is n (all nodes in the tree), so time complexity is O(n*logn).


Log in to reply
 

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