Simple solution using Java


  • 144
    R

    if the node does not exist, simply return 0. Otherwise, return the 1+the longer distance of its subtree.

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

  • 27
    D

    This is mine, just one line code:

    Recursion solution:

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

  • -9
    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if(!root)   return 0;
            if(!root->left)  return 1+maxDepth(root->right);
            if(!root->right) return 1+maxDepth(root->left);
            return 1+max(maxDepth(root->left), maxDepth(root->right));
        }
    };

  • 0
    T
    This post is deleted!

  • 0
    H

    nice,in this way it is beautiful


  • 4
    S

    We have the same solution, but it seems like the runtime of this solution only beat 10.77% of java submission. I wonder what is the most efficient solution.


  • 0
    A

    @S.C But I tried it, this solution beats 84.91% of java solution . lol


  • 0
    S

    @arafat324 Well, I think it's the problem of the internet then.


  • 1

    Got exactly the same code as yours :)


  • 0
    U

    @ray050899 Simple is beauty


  • 0
    public int maxDepth(TreeNode root) {
            if(root == null)
                return 0;
            return maxDepth(root.left)>maxDepth(root.right)?maxDepth(root.left)+1:maxDepth(root.right)+1;
        }
    

    Why does this code LTE?


  • 0
    J

    @kingwufeng
    maybe they changed the test case, or the configure of the test server.


  • 0

    and just for fun (I see everyone is taking the easy way out!) here is an iterative solution.

    
        public int MaxDepth(TreeNode root) {
            TreeNode node = root;
            Stack<TreeNode> nodeStack = new Stack<TreeNode>();
            Stack<int> depthStack = new Stack<int>();
            
            int max = 0;
            int depth = 1;
            while (node != null || nodeStack.Count > 0)
            {
                if (node != null)
                {
                    nodeStack.Push(node);
                    depthStack.Push(depth);
                    node = node.left;
                    depth++;
                }
                else
                {
                    node = nodeStack.Pop();
                    depth = depthStack.Pop();
                    
                    if (depth > max) max = depth;
                    
                    node = node.right;
                    depth++;
                }
            }
            
            return max;
        }
    

  • 0
    T

    @jdrogin
    Fails one of the test cases:
    Runtime Error Message:
    Line 26: java.util.NoSuchElementException
    Last executed input: [0]


  • 1

    @thepha3drus well my code was actually C#, but I converted to Java (nearly the same) and just tested it, it passes all tests and is accepted.

    here's the Java version

    
        public int maxDepth(TreeNode root) 
        {
            TreeNode node = root;
            Stack<TreeNode> nodeStack = new Stack<TreeNode>();
            Stack<Integer> depthStack = new Stack<Integer>();
            
            int max = 0;
            int depth = 1;
            while (node != null || !nodeStack.isEmpty())
            {
                if (node != null)
                {
                    nodeStack.push(node);
                    depthStack.push(depth);
                    node = node.left;
                    depth++;
                }
                else
                {
                    node = nodeStack.pop();
                    depth = depthStack.pop();
                    
                    if (depth > max) max = depth;
                    
                    node = node.right;
                    depth++;
                }
            }
            
            return max;
        }
    

  • 0
    C

    i did the same, but My code fails for this input tc
    Could someone help me figure out why?

    Thanks

    Your input
    [1,2,2,3,3,3,3,4,4,4,4,4,4,null,null,5,5]

    Your answer - false
    Expected answer - true

    
    
    public class Solution {
        public boolean isBalanced(TreeNode root) {
            return (maxDepth(root) - minDepth(root) <=1 );
        }
        
        public int maxDepth (TreeNode root){
            if(root == null) 
                return 0;
            else {int x =(1+ Math.max(maxDepth(root.left), maxDepth(root.right)));
                System.out.println(x);
                return  x;}
        }
        
        public int minDepth (TreeNode root){
            if(root == null) 
                return 0;
            else { int x = (1+ Math.min(minDepth(root.left), minDepth(root.right)));
                System.out.println(x);
                return  x;
                
            }
        }}   
    

  • 0
    C

    @dennyrong i did the same, but My code fails for this input tc
    Could you help me figure out why?

    Thanks

    Your input
    [1,2,2,3,3,3,3,4,4,4,4,4,4,null,null,5,5]

    Your answer - false
    Expected answer - true

    public class Solution {
    public boolean isBalanced(TreeNode root) {
    return (maxDepth(root) - minDepth(root) <=1 );
    }

    public int maxDepth (TreeNode root){
        if(root == null) 
            return 0;
        else {int x =(1+ Math.max(maxDepth(root.left), maxDepth(root.right)));
            System.out.println(x);
            return  x;}
    }
    
    public int minDepth (TreeNode root){
        if(root == null) 
            return 0;
        else { int x = (1+ Math.min(minDepth(root.left), minDepth(root.right)));
            System.out.println(x);
            return  x;
            
        }
    }}

  • 0
    M

    @kingwufeng maybe it is because the function enter root.left and root.right twice when you use "maxDepth(root.left)>maxDepth(root.right)?maxDepth(root.left)+1:maxDepth(root.right)+1", but i don't understand the reason about it.

    public class Solution {
    public int maxDepth(TreeNode root) {
    if(root==null)
    return 0;
    return dfs(root);
    }
    public int dfs(TreeNode root){
    if(root==null){
    return 0;
    }
    int f1=dfs(root.left);
    int f2=dfs(root.right);
    return f1>f2?f1+1:f2+1;
    }
    }


  • 0
    H

    is this some kind of dp solution?


  • 0
    G

    @ray050899 that's awesome! by the way,how can you consider recursive?


Log in to reply
 

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