Recursive solution, and iterative solution translated from the recursive solution


  • 0
    D

    My recursive solution leads to stack overflow. So I translated the recursive solution to iterative solution by following some mechanical steps. Then the stack overflow problem is solved. Maybe the next step is translating the iterative solution to a more semantically reasonable solution such that nobody can tell it is translated mechanically from recursive solution..

    Recursive solution:

    public class Solution {
        private int[] preorder;
        
        private int verifyPreorder(int index, Integer low, Integer high) {
            if (index == preorder.length) {
                return index;
            }
            int curNum = preorder[index];
            if ((low == null || low < curNum) && (high == null || curNum < high)) {
                int leftCallIndexRet = verifyPreorder(index + 1, low, curNum);
                return verifyPreorder(leftCallIndexRet, curNum, high);
            } else {
                return index;
            }
        }
        
        public boolean verifyPreorder(int[] preorder) {
            if (preorder == null || preorder.length == 0) {
                return true;
            }
            this.preorder = preorder;
            return verifyPreorder(0, null, null) == preorder.length;
        }
    }
    

    Iterative solution translated from the above recursive solution:

    public class Solution {
        private int[] preorder;
    
        private int verifyPreorder() {
            class Frame {
                int index;
                Integer low;
                Integer high;
                boolean leftCall;
                Frame(int index, Integer low, Integer high, boolean leftCall) {
                    this.index = index;
                    this.low = low;
                    this.high = high;
                    this.leftCall = leftCall;
                }
                Integer ret;
            }
            Stack<Frame> stack = new Stack<>();
            stack.push(new Frame(0, null, null, false));
    
            do {
                if (stack.peek().ret == null) {
                    int index = stack.peek().index;
                    Integer low = stack.peek().low;
                    Integer high = stack.peek().high;
    
                    if (index == preorder.length) {
                        stack.peek().ret = index;
                    } else {
                        int curNum = preorder[index];
                        if ((low == null || low < curNum) && (high == null || curNum < high)) {
                            stack.push(new Frame(-1, curNum, high, false));
                            stack.push(new Frame(index + 1, low, curNum, true));
                        } else {
                            stack.peek().ret = index;
                        }
                    }
                } else {
                    Frame frame = stack.pop();
                    int ret = frame.ret;
                    boolean leftCall = frame.leftCall;
                    if (leftCall) {
                        stack.peek().index = ret;
                    } else {
                        stack.peek().ret = ret;
                    }
                }
            } while (stack.size() > 1);
    
            return stack.pop().ret;
        }
    
        public boolean verifyPreorder(int[] preorder) {
            if (preorder == null || preorder.length == 0) {
                return true;
            }
            this.preorder = preorder;
            return verifyPreorder() == preorder.length;
        }
    }
    

Log in to reply
 

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