Java Solution, MaxDepth


  • 67

    For every node, length of longest path which pass it = MaxDepth of its left subtree + MaxDepth of its right subtree.

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

  • 10

    same here without the member variable using 2 value return instead.

        public int DiameterOfBinaryTree(TreeNode root) {
            return DFS(root)[0];
        }
        
        // int[2] = [best, height]
        private int[] DFS(TreeNode node)
        {
            if (node == null) return new int[] { 0, 0 };
            int[] left = DFS(node.left);
            int[] right = DFS(node.right);
            
            int best = Math.Max(left[1] + right[1], Math.Max(left[0], right[0]));
            int height = 1 + Math.Max(left[1], right[1]);
            return new int[] { best, height };
        }
    

  • 0
    Z

    Same thought here, it's basically a height counting problem.

    public class Solution {
        int max;
        public int diameterOfBinaryTree(TreeNode root) {
            max = 0;
            height(root);
            return max;
        }
        int height(TreeNode root){
            if(root==null)return -1;
            int leftH = height(root.left);
            int rightH = height(root.right);
            int height = Math.max(leftH,rightH)+1;
            max = Math.max(max,leftH+rightH+2);
            return height;
        }
    }
    

  • 8
    M

    I want to give some explanation.

    We want to compare all diameters among all subtrees.
    Then this can be done when we DFS traverse the root.
    We just need to record the maximum one in a variable.

    In this post, the variable is the int max.
    max = Math.max(max, left + right) is to compare whether the diameter of this subtree is max or not, if it is, record it.
    And the remaining part in the maxDepth is just the normal height counting.

    Additionally, this is the C++ version:

    class Solution {
        int get_height(TreeNode* root)
        {
            if (!root) return 0;
            int height_left = get_height(root->left);
            int height_right = get_height(root->right);
            if (height_left + height_right > max_diameter) {
                max_diameter = height_left + height_right;
            }
            return max(height_left, height_right) + 1;
        }
        int max_diameter = 0;
        
    public:
        int diameterOfBinaryTree(TreeNode* root) {
            if (!root) return 0;
            int height = get_height(root);
            return max_diameter;
        }
    };
    

  • -1
    P

    Its giving number of edges as output in the answer. But the definition of diameter of tree is number of nodes along the path. Can somebody enlighten me.


  • 1

    @parteek Per the problem, the diameter of a binary tree is the length of the longest path between any two nodes in a tree.


  • 8

    Similar solution. But your codes looks clearer.

    public int diameterOfBinaryTree(TreeNode root) {
            int res = 0;
            if(root == null) return res;
            
            // int cur = Math.max(maxDepth(root.left), maxDepth(root.right)) + Math.min(maxDepth(root.left), maxDepth(root.right));
            int cur = maxDepth(root.left) + maxDepth(root.right);
            int left = diameterOfBinaryTree(root.left);
            int right = diameterOfBinaryTree(root.right);
     
            return Math.max(cur, Math.max(left, right));
        }
        public int maxDepth(TreeNode root){
            if(root == null) return 0;
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    

    Updated:
    Thanks to @shawngao to make it clearer.


  • 0

    @Tōsaka-Rin said in Java Solution, MaxDepth:

    int cur = Math.max(maxDepth(root.left), maxDepth(root.right)) + Math.min(maxDepth(root.left), maxDepth(root.right));

    Why bother getting a max from two numbers, getting a min from the same two numbers and then plus them together? Isn't your code equals to:

    int cur = maxDepth(root.left) + maxDepth(root.right)); ?

    Also, here:

    res = Math.max(res, Math.max(cur, Math.max(left, right)));
    return res;

    You can write it like this:

    return Math.max(cur, Math.max(left, right));

    Because res is always 0, you don't need to compare it with cur, left or right.


  • 0
    Z

    @shawngao Hello I came up with the same idea with yours. However, there is one problem I don't understand. If you change your second line to

    static int max = 0;
    

    and hit "submit solution", you can see that the program fails on the case of []. But when you click "Run Code" with input of [], the answer is totally correct. Do you know why the program fails on the case of [] when I submit it with static keyword?


  • 3

    @zd19900410

    To understand this problem, you need to know how LeetCode judge call your program and what the static keyword mean.

    1. When you click Run Code / Submit, LeetCode judge will first create an instance of your Solution class i.e. Solution s = new Solution() then call the specific function, s.diameterOfBinaryTree() in this case, and pass in one test case each time. s will be destroyed / GCed after the run. The difference is Run Code only has one test case to test but Submit will repeat those steps for every test case.
    2. The static keyword will make the variable max not be initialized across different test cases. Meaning when the 2nd test case starts, max will still have the value at the end of 1st test case. As you can see when it is failed:

    Input:
    []
    Output:
    3
    Expected:
    0

    It is obvious that max = 3 at the end of the previous test case of [].


  • 0
    H

    @zd19900410 said in Java Solution, MaxDepth:

    @shawngao Hello I came up with the same idea with yours. However, there is one problem I don't understand. If you change your second line to

    static int max = 0;
    

    and hit "submit solution", you can see that the program fails on the case of []. But when you click "Run Code" with input of [], the answer is totally correct. Do you know why the program fails on the case of [] when I submit it with static keyword?

    This is because the static field is only initialized once after its containing class is loaded by the classloader. During the lifecycle of one JVM process, your class only gets load once and the static field keeps the value from the previous test. If the tree used each time is getting bigger, this is not an issue. If the tree is smaller than the previous one like [], your method will fail.


  • 0
    H

    @shawngao said in Java Solution, MaxDepth:

    @zd19900410

    To understand this problem, you need to know how LeetCode judge call your program and what the static keyword mean.

    1. When you click Run Code, LeetCode judge will first create an instance of your Solution class i.e. Solution s = new Solution() then call the specific function, s.diameterOfBinaryTree() in this case, and pass in only one test case. s will be destroyed / GCed after the run.
    2. When you click Submit Solution, LeetCode judge will first create an instance of your Solution class i.e. Solution s = new Solution() then call the specific function, s.diameterOfBinaryTree() in this case, and pass in many test cases. The same s instance will be used to test all those test cases.
    3. The static keyword will make the variable max not be initialized across different test cases. Meaning when the 2nd test case starts, max will still have the value at the end of 1st test case. As you can see when it is failed:

    Input:
    []
    Output:
    3
    Expected:
    0

    It is obvious that max = 3 at the end of the previous test case of [].

    Your explanation is incorrect. If you change the static field max to non static one, all test cases will pass. I did it in this way. It's obvious that the server will re-create a new instance for each test case. The real reason has been given above by me.


  • 0

    @hwd2000 you are so fast, I am still modifying my reply :)


  • 0
    H

    @shawngao said in Java Solution, MaxDepth:

    @hwd2000 you are so fast, I am still modifying my reply :)

    Lol. I happened to finish this question minutes ago and found your answer is exactly like what I have written. Then I found the question above.


  • 0
    C

    Hi! I really like your solution, there is just one thing that I don't understand why do we have to define two variables: left, and right here. When I directly used max = Math.max(max, maxDepth(root.left)+maxDepth(root.right)); return Math(maxDepth(root.left),maxDepth(root.right))+1; I got TLE.


  • 0

    @cqy0118 Doing things multiple times instead of just once might take more time? Inconceivable!


  • 0
    C

    Hi, I don't quite understand why we need to return max(leftHeight, rightHeight)+1;, I initially wrote return max(leftHeight, rightHeight); which is wrong. Thanks

    Input:
    [1,2,3,4,5]
    Output:
    2
    Expected:
    3

    class Solution {
    public:
    int diameterOfBinaryTree(TreeNode* root) {
        int res = 0;
        
        dfs(root, res);
        
        return res;
    }
    
    int dfs(TreeNode* cur, int& res){
        if (cur==NULL)
           return 0;
           
        if (cur->left==NULL && cur->right==NULL)
           return 1;
           
        int leftHeight = dfs(cur->left, res), rightHeight = dfs(cur->right, res);
        
        int len = leftHeight + rightHeight;
        
        res = max(res, len);
        return max(leftHeight, rightHeight)+1;
    }
    

    };


  • 0

    @coder2 What we want to return is the MaxDepth of current node. Doesn't it equal to max(leftMaxDepth, rightMaxDepth) + 1?


  • 0
    C

    I think I'm confused about the definition of the parameter/path with the depth. :(


  • 0
    D

    same idea with you

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int diameterOfBinaryTree(TreeNode root) 
        {
            int[] maxDiameter = new int[1];
            helper(root, maxDiameter);
            return maxDiameter[0];
        }
        
        private int helper(TreeNode n, int[] md)
        {
            // base case
            if (n == null || (n.left == null && n.right == null)) { return 0; }
            
            // get the left side path length
            int leftLen = 0;
            if (n.left != null)
            {
                leftLen = 1 + helper(n.left, md);
            }
            
            // get the right side path length
            int rightLen = 0;
            if (n.right != null)
            {
                rightLen = 1 + helper(n.right, md);
            }
            // record current longest diameter
            md[0] = Math.max(md[0], leftLen + rightLen);
            // return max one
            return Math.max(leftLen, rightLen);
        }
    }
    

Log in to reply
 

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