C++ O(n) Time and O(1) Space recursion solution


  • -1
    Y
    class Solution {
    /*The logic is that if the right child contains node whose value is smaller than that of current node, then the given order is invalid. */
    public:
        bool verifyPreorder(vector<int>& preorder) {
            if(preorder.size() <= 1)
                return true;
            int n = preorder.size();
            bool ispreorder = true;
            dfs(0, 1, n, ispreorder, preorder);
            return ispreorder;
        }
    
    private:
        int dfs(int root_idx, int sta_idx, int end_idx, bool &ispreorder, vector<int>& preorder){
            if(sta_idx >= end_idx)
                return preorder[root_idx];
            int idx = sta_idx, min_val;
            for(; idx < end_idx; ++ idx){
                if(preorder[idx] > preorder[idx - 1])
                    break;
            }
            //only has left child
            if(idx >= end_idx){
                return preorder[end_idx - 1];
            }
            //only has right child
            if(idx == sta_idx){
                min_val = dfs(root_idx + 1, sta_idx + 1, end_idx, ispreorder, preorder);
                if(min_val < preorder[root_idx] || ispreorder == false){
                    ispreorder = false;
                }
                return min(min_val, preorder[root_idx]);
            }
            
            int nxt_idx = idx;
            for(; nxt_idx < end_idx; ++ nxt_idx){
                if(preorder[nxt_idx] > preorder[root_idx])
                    break;
            }
            //only has left child
            if(nxt_idx >= end_idx){
                //check the right child of current node's left child
                min_val = dfs(idx, idx + 1, end_idx, ispreorder, preorder);
                if(min_val < preorder[idx - 1] || ispreorder == false){
                    ispreorder = false;
                }
                return min(min_val, preorder[idx - 1]);
            }
            //check right child first
            min_val = dfs(nxt_idx, nxt_idx + 1, end_idx, ispreorder, preorder);
            if(min_val < preorder[root_idx] || ispreorder == false){
                ispreorder = false;
                return preorder[root_idx];
            }
            //then check the right child of current node's left child
            min_val = dfs(idx, idx + 1, nxt_idx, ispreorder, preorder);
            if(min_val < preorder[idx - 1] || ispreorder == false){
                ispreorder = false;
            }
            return min(min_val, preorder[idx - 1]);
        }
    };

  • 0
    T
    This post is deleted!

  • 0
    T
    #define SIZE(container) (int)(container).size()
    
    // Tian Xia
    class Solution {
     public:
      typedef int   Position;
      typedef int   Value;
    
      bool verifyPreorder(vector<int>& preorder) {
        if (SIZE(preorder) <= 2) {
          return true;
        }
    
        Value minv, maxv;
        auto ret = traverse_son(preorder, 0, INT_MAX, minv, maxv);
    
        return ret != -1;
      }
    
     protected:
      Position traverse_son(const vector<int> &preorder, 
                            Position pos, Value bound, 
                            Value &minv, Value &maxv) {
        Value root = preorder[pos]; 
        Value left_min, left_max, right_min, right_max;
        Position right_start = pos + 1;
        minv = maxv = root;
    
        if (pos + 1 >= SIZE(preorder)) {
          return right_start; 
        }
        else if (preorder[pos + 1] < root) {
          right_start = traverse_son(preorder, pos + 1, root, left_min, left_max);
          if (right_start == -1 || left_max > root) {
            return -1;
          }
          minv = left_min;
        }
    
        if (right_start == SIZE(preorder) || preorder[right_start] > bound) {
          return right_start;
        }
        else {
          Position next_tree_start = traverse_son(preorder, right_start, bound, 
                                                  right_min, right_max);
          if (next_tree_start == -1 || right_min < root) {
            return -1;
          }
          maxv = right_max;
          return next_tree_start;
        }
      }
    };
    

Log in to reply
 

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