255. Verify Preorder Sequence in Binary Search Tree

leetcode medium

#array#csharp#leetcode#medium#search#stack#tree

Task

Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.

Пример:

Input: preorder = [5,2,1,3,6]

Output: true

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public bool VerifyPreorder(int[] preorder) {
        int minLimit = int.MinValue;
        Stack<int> stack = new Stack<int>();
        
        foreach (int num in preorder) {
            while (stack.Count > 0 && stack.Peek() < num) {
                minLimit = stack.Pop();
            }
            
            if (num <= minLimit) {
                return false;
            }
            
            stack.Push(num);
        }
        
        return true;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool VerifyPreorder(vector<int>& preorder) {
        int minLimit = int.MinValue;
        stack<int> stack = new stack<int>();
        
        foreach (int num in preorder) {
            while (stack.size() > 0 && stack.Peek() < num) {
                minLimit = stack.pop();
            }
            
            if (num <= minLimit) {
                return false;
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

Java solution

matched/original

import java.util.Stack;

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int minLimit = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        
        for (int num: preorder) {
            while (!stack.isEmpty() && stack.peek() < num) {
                minLimit = stack.pop();
            }
            
            if (num <= minLimit) {
                return false;
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

JavaScript solution

matched/original

class Solution {
    verifyPreorder(preorder) {
        let minLimit = -Infinity
        const stack = []
        
        for (const num of preorder) {
            while (stack.length && stack[stack.length - 1] < num) {
                minLimit = stack.pop()
            }
            
            if (num <= minLimit) {
                return false
            }
            
            stack.push(num)
        }
        
        return true
    }
}

Python solution

matched/original

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        minLimit = float('-inf')
        stack = []
        
        for num in preorder:
            while stack and stack[-1] < num:
                minLimit = stack.pop()
            
            if num <= minLimit:
                return False
            
            stack.append(num)
        
        return True

Go solution

matched/original

package main

func verifyPreorder(preorder []int) bool {
    minLimit := -1 << 31
    stack := []int{}
    
    for _, num := range preorder {
        for len(stack) > 0 && stack[len(stack)-1] < num {
            minLimit = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        
        if num <= minLimit {
            return false
        }
        
        stack = append(stack, num)
    }
    
    return true
}

Explanation

Algorithm

1️⃣

Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек.

2️⃣

Итерируйте по массиву preorder. Для каждого num:

Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit.

Если num <= minLimit, верните false.

Добавьте num в стек.

3️⃣

Верните true, если удалось пройти весь массив.

😎