Binary search tree after the order traversal sequence

The title

Input an array of integers to determine whether the array is the result of a binary search tree traversal. Return true if yes, false otherwise. Assume that any two digits in the input array are different from each other.

Refer to the following binary search tree:

Example 1:

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

Example 2:

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

Preparatory knowledge

Traversal of a binary tree

The depth-first traversal of a binary tree can be subdivided into pre-ordered traversal, middle-ordered traversal, and post-ordered traversal, which can be implemented recursively or non-recursively.

Root -> left subtree -> right subtree (root -> left -> right)

In order traversal: left subtree -> root node -> right subtree (left -> root -> right)

After order traversal: left subtree -> right subtree -> root node (left -> right -> root)

1. Preorder traversal

The root node -> the left subtree -> the right subtree. Note that the code printf is placed before the two recursive statements, so first access the root node G, print G, then access the left subtree D, and then the left subtree D as the root node, print D, then access the left subtree A of D

And as A root node, print A, A no left subtree or right subtree, function call to return to the end of D node (GDA) are already printed D node left subtree is recursive, now recursive access right subtree F, F as A root node, print F, F has left subtree visit left subtree E, E

The left subtree of F has recursed, but there is no right subtree. So the function ends recursion and returns the D node. The left subtree of F has recursed, but there is no right subtree.

Function recursive end return G nodes, node access G right subtree of M, M as a root node, print M, visit M left subtree H, H as a root node, print H, (already printed are: GDAFEMH) H no right sub tree and left subtree, function recursive over, return to M nodes, M node subtree has already left

Recursion is completed, access right subtree Z, Z as a root node, print Z, Z no right sub tree and left subtree, function recursive over, return to M nodes, M nodes left subtree right subtree recursion is complete, function recursive over, return to G nodes, left and right subtrees of G node recursive is complete, the binary tree traversal is over

Preorder traversal result: GDAFEMHZ

Summarize the preorder traversal steps

Step 1: Print the node

Step 2: Access the left subtree, returning to step 1 (note: Return to step 1 means that the left subtree of the root node is the new root node, just as D is the left subtree of G, but D is also the root of A and F nodes)

Step 3: Access the right subtree, returning to step 1

Step 4: End the recursion and return to the previous node

Another statement of preorder traversal:

(1) Access the root node

(2) Preorder traversal of the left subtree

(3) Preorder traversal right subtree

(In the completion of step 2 and 3, also in accordance with the previous order through the binary tree rule to complete)

2. Sequence traversal (the detailed traversal process will not be repeated, (┬ _ ┬))

Step 1: Access the left subtree of this node

Step 2: Return step 1 if the node has a left subtree, otherwise print the node

Step 3: Return step 1 if the node has a right subtree, otherwise end the recursion and return the previous node

(In my own understanding of the middle order: first left to bottom, left to no left stop and print the node, then return to the node before the node, print the node, then access the node’s right subtree, left to no left stop)

Another statement of ordered traversal in:

(1) in order to traverse the left subtree

(2) Access the root node

(3) in order to traverse the right subtree

(At the completion of steps 1 and 3, follow the rule of order traversal in)

Therefore, the sequence traversal in the figure is: ADEFGHMZ

3. The sequence of traversal step

Step 1: Access the left subtree

Step 2: If the node has a left subtree, return step 1

Step 3: If the node has a right subtree, return step 1, otherwise print the node and return the previous node

Another statement of post-ordered traversal:

(1) The left subtree is traversed in the sequential order

(2) After order traversal right subtree

(3) Access the root node

(When completing step 1 and Step 2, follow the rule of sequential traversal.)

The sequential traversal of the graph is: AEFDHZMG

Online to find some more reconstruction of binary tree exercises, help deepen the understanding of the above three traversal tree process

Important concepts

Binary search tree features: the left subtree is smaller than the root node and the right subtree

Antithesis thought

After understanding the above knowledge point, review the problem, since it is a back-order traversal, then, the last array must be the root node, for example, given the array [1,3,2,6,5], then 5 is the root node, according to the characteristics of binary search tree, 1,3 is the left subtree,2,6,5 is the right subtree. At the same time, each subtree has to satisfy the appeal condition, so the recursive lookup judgment comes naturally. Once you understand these principles, it’s easy to implement them in code.

Code implementation

/** * @param {number[]} postorder * @return {boolean} */ var verifyPostorder = function(postorder) { if (! postorder.length) return true; // Return true const root = postorder[postorder.length - 1]; Const leftTree = [], rightTree = []; // The left subtree of the root node is all smaller than the root node, and the right subtree of the root node is all larger than the root node. Let cIndex = null; // Let cIndex = null; // Let cIndex = null; // Record the dividing point of the left and right subtrees, i.e. the first node satisfying the right subtree, Every ((item, index) => {if (index === postorder.length - 1) return true; If (cIndex === null && item > root) {cIndex = index; } if (cIndex! == null) {// if cIndex! == null, indicating that the node in the right subtree has been traversed, then judge the following tree according to the rule of the right node (the value of the right subtree should be greater than the root node), and push the following nodes into the array of the right subtree. If (index >= cIndex) {rightTree. Push (item); return item > root; }} else {// if cIndex === null, if cIndex === null, then lefttree. push(item); return item < root; } }) if (! flag) return false; Let left = true, right = true; if (leftTree.length) { left = verifyPostorder(leftTree); } if (rightTree. Length) {right = verifyPostorder(rightTree); // Return left && right; // Return left && right; // Return true if both left and right are true;