Java 11ms Recursive Solution


  • 0
    public class Solution {
        public int diameterOfBinaryTree(TreeNode root) {
            return helper(root,0);
        }
        public int helper(TreeNode root, int res){
            //for each node, get its left subtree height and right subtree height
            //return the maximum (left subtree height + right subtree height)
            if(root == null)return res;
            int lH = getHeight(root.left, 0);
            int rH = getHeight(root.right, 0);
            if(lH + rH >= res) res = lH + rH;
            else return res;//if the current diameter is the maximum, stop searching subtrees.
            int l = helper(root.left, res);
            int r = helper(root.right, res);
            return Math.max(l,r);
        }
        public int getHeight(TreeNode root, int height){
            if(root == null)return height;
            int l = getHeight(root.left, height+1);
            int r = getHeight(root.right, height+1);
            return Math.max(l,r);
        }
    }
    

Log in to reply
 

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