Java solution, both recursion and iteration


  • 2
    H
    public int minDepth(TreeNode root) {
        // recursion method
        if (root == null) return 0;
        int count = 1;
        if (root.left == null && root.right != null) {
            return minDepth(root.right) + 1;
        }
        if (root.left != null && root.right == null) {
            return minDepth(root.left) + 1;
        }
        return helper(root);
    }
    private int helper(TreeNode root) {
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
    

    public int minDepth(TreeNode root) {
        // iteration method
        if (root == null) return 0;
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> levels = new Stack<>();
        stack.push(root);
        levels.push(1);
        int min = Integer.MAX_VALUE;
        while (!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            int level = levels.pop();
            if (temp.left == null && temp.right == null) {
                min = Math.min(min, level);
            }
            if (temp.left != null) {
                stack.push(temp.left);
                levels.push(level + 1);
            }
            if (temp.right != null) {
                stack.push(temp.right);
                levels.push(level + 1);
            }
        }
        return min;
    }

  • 0
    L

    Hi, thank you for your sharing. Could you please explain what is the time and space complexity for both recursive and iterative version?


Log in to reply
 

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