Java O(n) Solution


  • 0
    M

    This solution uses a global variable which is not good. To remove it, we may wrap "max" in return result and parse it to the inputs of the recursive calls.

    public class Solution {
        int max = 1;
        public int diameterOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            check(root);
            return max - 1;
        }
        private int check(TreeNode root) {
            if (root == null) return 0;
            int left = check(root.left), right = check(root.right);
            int len = left + right + 1;
            max = Math.max(max, len);
            return Math.max(left, right) + 1;
        }
    }
    

Log in to reply
 

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