leetcode: 255 Verify preorder traversal sequence binary search tree

题目来源

• leetcode：255-VIP 验证前序遍历序列二叉搜索树

题目描述

给定一个整数数组,你需要验证它是否是一个二叉搜索树正确的先序遍历序列.
你可以假定该序列中的数都是不相同的.

参考以下这颗二叉搜索树：

示例 1：
输入: [5,2,6,1,3]
输出: false

示例 2：
输入: [5,2,1,3,6]
输出: true

题目解析

思路

• 二叉搜索树的特点是： 左子树的值 < 根节点的值 < 右子树的值
• So the in-order traversal must be an ordered array,But the former sequence traversal what law？Its preorder traversal array is locally decreasing,Increasing the overall array
• 所以可以借助单调栈
  • set a minimum value low,然后遍历数组,If the current value is less than this minimum low,返回 false
  • 对于根节点,将其压入栈中,然后往后遍历
    • If the number encountered is less than the top element of the stack,Description is the point of its left subtree,继续压入栈中
    • until the encountered number is greater than the top element of the stack,Then the value on the right is.Which is need to find the right child node tree,所以更新 low value and delete the top element of the stack,Then continue to compare with the next top element of the stack,如果还是大于,则继续更新 low Value and cut out the top,Until the stack is empty or greater than the current value to stop the current stack elements,push current value
  • In this way, if it does not return before traversing the entire array false 的话,最后返回 true 即可

class Solution {
    
public:
    bool verifyPreorder(vector<int>& preorder) {
    
        if(preorder.size() <= 2) return true;
        int MIN = INT32_MIN;
        stack<int> s;
        for(int i = 0; i < preorder.size(); ++i)
        {
    
            if(preorder[i] < MIN)
                return false;
            while(!s.empty() && s.top() < preorder[i])//met a big one,右分支
            {
    
                MIN = s.top();//The top of the record stack is the minimum value
                s.pop();
            }
            s.push(preorder[i]);
        }
        return true;
    }
};

进阶要求

In order to keep the space complexity constant,我们不能使用 stack,所以直接修改 preorder,将 low 值存在 preorder specific location

class Solution {
    
public:
    bool verifyPreorder(vector<int>& preorder) {
    
        int low = INT_MIN, i = -1;
        for (auto a : preorder) {
    
            if (a < low) return false;
            while (i >= 0 && a > preorder[i]) {
    
                low = preorder[i--];
            }
            preorder[++i] = a;
        }
        return true;
    }
};

分治法

• Maintain a lower bound in the recursive functions lower 和上界 upper,Then the currently traversed node must be in(low, upper)之间
• Then search for the first one in the given interval>=point of current value,以此为分界点,Call the recursive function on the left and right sides respectively.Note the left half upper Update to current node value val,Indicates that the node value of the left subtree must be less than the current node value,while the right half of the recursive lower Update to current node value val,Indicates that the node value of the right subtree must be greater than the current node value
• If both the left and right parts return true,returns true as a whole

class Solution {
    
public:
    bool verifyPreorder(vector<int>& preorder) {
    
        return helper(preorder, 0, preorder.size() - 1, INT_MIN, INT_MAX);
    }
    bool helper(vector<int>& preorder, int start, int end, int lower, int upper) {
    
        if (start > end) return true;
        int val = preorder[start], i = 0;
        if (val <= lower || val >= upper) return false;
        for (i = start + 1; i <= end; ++i) {
    
            if (preorder[i] >= val) break;
        }
        return helper(preorder, start + 1, i - 1, lower, val) && helper(preorder, i, end, val, upper);
    }
};