LC: 255. Verify Preorder Sequence in Binary Search Tree
https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
255. Verify Preorder Sequence in Binary Search Tree
Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.
Example 1:
Input: preorder = [5,2,1,3,6]
Output: trueExample 2:
Input: preorder = [5,2,6,1,3]
Output: falseConstraints:
1 <= preorder.length <= 1041 <= preorder[i] <= 104All the elements of
preorderare unique.
Follow up: Could you do it using only constant space complexity?
Verify Preorder Sequence in Binary Search Tree
The Essence:
Man muss auf die Eigenschaften der Binärbäume beachten: Der linke Unterbaum eines Knotens enthält nur kleinere Werte, wohingegen der rechte Unterbaum nur größere Werte enthält. Die Folge der Zahlen müssen also immer von oben oder von unten beschränkt werden, je nachdem, ob wir sie als linken oder rechten Unterbaum verarbeiten
Details:
Man kann die beschränkenden Zahlen in einem Stapel oder in einem Variable speichern. Außerdem kann man das Eingabe-Array auch als Stapel verwenden oder die Beschränkungen durch Rekursion implementieren.
Solution(s) and Further Explanation:
The code:
Default Code:
Last updated