A Single-Line C# Recur Solution and a concise Stack Iterative Solution


  • 0
    L
    public int MaxDepth(TreeNode root) {
        return root == null ? 0 : Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
    }

  • 0
    L
    //An iterative solution by building a new TreeNode type with Depth attached
    public int MaxDepth(TreeNode root) {
        if (root == null) return 0;
        int maxDepth = 0;
        Stack<DepthNode> stack = new Stack<DepthNode>();
        stack.Push(new DepthNode() { Node = root, Depth = 1 });
        while(stack.Count != 0)
        {
            DepthNode dn = stack.Pop();
            if (dn.Depth > maxDepth) maxDepth = dn.Depth;
            if (dn.Node.right != null) stack.Push(new DepthNode() {Node = dn.Node.right, Depth = dn.Depth + 1});
            if (dn.Node.left != null)
            {
                dn.Node = dn.Node.left;
                dn.Depth++;
                stack.Push(dn);
            }
        }
        return maxDepth;
    }
    private class DepthNode
    {
        public TreeNode Node { get; set; }
        public int Depth { get; set; }
    }

  • 0

    How about going level by level? Should be simpler, as you only need to store a list of regular nodes for each level.


  • 0
    L

    Here we go. This is shorter.

    public int MaxDepth(TreeNode root) {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        int maxDepth;
        queue.Enqueue(root);
        for(maxDepth = 0;root != null && queue.Count != 0; maxDepth++)
            for(int curCount = queue.Count; curCount > 0; curCount--)
            {
                TreeNode cur = queue.Dequeue();
                if (cur.left != null) queue.Enqueue(cur.left);
                if (cur.right != null) queue.Enqueue(cur.right);
            }
        return maxDepth;
    }

  • 0

    Nice. And better than what I had in mind :-)


  • 0
    B

    I came up with following which is very similar. Why it's not accepted because of "Time Limit Exceeded"?

        //    public int MaxDepth(TreeNode root)
        //    {
        //        if (root != null)
        //        {
        //            return MaxDepth(root.left) > MaxDepth(root.right) ? 1 + MaxDepth(root.left) : 1 + MaxDepth(root.right);
        //        }
        //        else
        //        {
        //            return 0;
        //        }
        //    }

  • 0
    L

    Hi breezeZ, your solution makes recursive twice per node call. Changing to below fixes it.

        public int MaxDepth(TreeNode root)
        {
            if (root != null)
            {
                int cLeft = MaxDepth(root.left), cRight = MaxDepth(root.right);
                return cLeft > cRight ? 1 + cLeft : 1 + cRight;
            }
            else
            {
                return 0;
            }
        }
    

  • 0
    B

    Now it's very obvious :). Thanks!


Log in to reply
 

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