Java solution, both recursion and iteration


  • 14
    H
    // iteration method
    public int maxDepth(TreeNode root) {
        int max = 0;
        if (root == null) {return 0;}
        Stack<TreeNode> path = new Stack<>();
        Stack<Integer> sub = new Stack<>();
        path.push(root);
        sub.push(1);
        while (!path.isEmpty()) {
            TreeNode temp = path.pop();
            int tempVal = sub.pop();
            if (temp.left == null && temp.right == null) {max = Math.max(max, tempVal);}
            else {
                if (temp.left != null) {
                    path.push(temp.left);
                    sub.push(tempVal + 1);
                }
                if (temp.right != null) {
                    path.push(temp.right);
                    sub.push(tempVal + 1);
                }
            }
        }
        return max;
    }
    

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

  • 1
    S

    My alternative non-recursive solution.

        public class Solution {
        public int maxDepth(TreeNode root) {
            if(root==null) return 0;
            int depth=0;
            Queue<TreeNode> queue=new LinkedList<TreeNode>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int levelSize=queue.size();
                depth++;
                for(int i=0;i<levelSize;i++){
                    TreeNode top=queue.poll();
                    if(top.left!=null) queue.offer(top.left);
                    if(top.right!=null) queue.offer(top.right);
                }
            }
            return depth;
        }
    }

Log in to reply
 

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