RUST GYM Leetcode 255 Verify Preorder Sequence in Binary Search Tree Rust Solution

255. Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Consider the following binary search tree:

Example 1:

Input: [5,2,6,1,3]
Output: false

Example 2:

Input: [5,2,1,3,6]
Output: true

Follow up:
Could you do it using only constant space complexity?

Rust Solution

struct Solution;

impl Solution {
    fn verify_preorder(preorder: Vec<i32>) -> bool {
        let mut low = std::i32::MIN;
        let mut stack: Vec<i32> = vec![];
        for x in preorder {
            if x < low {
                return false;
            }
            while let Some(&top) = stack.last() {
                if top < x {
                    stack.pop();
                    low = top;
                } else {
                    break;
                }
            }
            stack.push(x);
        }
        true
    }
}

#[test]
fn test() {
    let preorder = vec![5, 2, 6, 1, 3];
    let res = false;
    assert_eq!(Solution::verify_preorder(preorder), res);
    let preorder = vec![5, 2, 1, 3, 6];
    let res = true;
    assert_eq!(Solution::verify_preorder(preorder), res);
}

Having problems with this solution? Click here to submit an issue on github.