33. Order traversal sequence of binary search tree

“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

Hi 👋

• Wechat: RyukieW
• Wechat official account: LabLawliet
• 📦 Archive of technical articles
• 🐙 making

More columns:

The independent development of Lawliet

Lawliet’s iOS garden party

Lawliet’s underlying iOS lab

Lawliet’s iOS Reverse lab

Lawliet’s brush book

The title

Enter an array of integers to determine if the array is the result of a sequential traversal of a binary search tree. Returns true if it is, false otherwise. Suppose that any two numbers in the input array are different.

Consider the following binary search tree:

      5
     / \
    2   6
   / \
  1   3
Copy the code

Example 1:

Input: [1,6,3,2,5] output: falseCopy the code

Example 2:

Input: [1,3,2,6,5] output: trueCopy the code

Tip: Array length <= 1000

Source: LeetCode

What is a binary search tree?

Binary Search Tree (BST), also known as Binary sort Tree or Binary Search Tree.

A binary tree, which can be empty; If it is not empty, it satisfies the following properties:

• Non-empty left subtreeAll key values ofLess thanitsThe root nodeThe key value
• Non-empty right subtreeAll key values ofIs greater thanitsThe root nodeThe key value
• Left and right subtreesAre allBinary search tree

Analysis of the

Given the properties of the binary search tree, we know that the structure of the result of its post-order traversal is

• Left node set A right node set B root nodeAn array of elements so distributed
• andAAll elements of, are less than,BIs greater than the following node
• whileA 、 BIt isBinary search treeI can solve this recursively, and I can convert the problem to zeroCheck whether the results of all subtrees meet the requirements

solution

func verifyPostorder(_ postorder: [Int]) -> Bool {
    guard let root = postorder.last else {
        return true
    }
    var left: [Int] = []
    var right: [Int] = []
    var flag = false
    
    for offset in 1..<postorder.count {
        let v = postorder[postorder.count - 1 - offset]
        if v < root {
            if flag = = false { flag = true }
            left.insert(v, at: 0)}else if v > root, flag = = false {
            right.insert(v, at: 0)}else {
            return false}}return verifyPostorder(left) && verifyPostorder(right)
}
Copy the code

👋 Welcome to like and follow ♥️