Is the iterative solution better than its recursive counterpart?


  • 4
    3

    While the recursive version itself is concise, I was trying to see if an iterative solution will be better in terms of performance: I used an additional stack of integer to store the current path length while proceeding the pre-order traversal of the tree and keep the max depth updated. Though the result tends to be even slower... anyone got more effective iterative code for this problem? thx.

    public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        //int l = maxDepth(root.left);
        //int r = maxDepth(root.right);
        //return Math.max(l, r) + 1;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Stack<Integer> stackLength = new Stack<Integer>();
        stack.push(root);
        stackLength.push(1);
        int max = 0;
        while(stack.size() != 0)
        {
            TreeNode cur = stack.pop();
            int pathLength = stackLength.pop();
            max = Math.max(max, pathLength);
            if(cur.right != null)
            {
                stack.push(cur.right);
                stackLength.push(pathLength + 1);
            }
            if(cur.left != null)
            {
                stack.push(cur.left);
                stackLength.push(pathLength + 1);
            }
        }
        return max;
    }

  • 0
    A

    What a prefect solution :),Although the TreeNode class does not have a visited variable,by adding an extra stack keeps track of the levels is a very brilliant idea.


Log in to reply
 

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