Interview question 26: post order traversal sequence of binary search tree

Knock algorithm series articles

"Leetcode : https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof

"GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_26_verifyPostorder/Solution.java

Sword finger Offer 26 Postorder traversal sequence of binary search tree

Title Description: enter an integer array to judge whether the array is the post order traversal result of a binary search tree. If yes, it returns true; otherwise, it returns false. Suppose that any two numbers of 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

Problem solving ideas:

Definition of post order traversal: [left subtree | right subtree | root node], that is, the traversal order is "left, right and root".
Binary search tree definition:
- The value of all nodes in the left subtree < the value of the root node;
- The value of all nodes in the right subtree > the value of the root node;
- The left and right subtrees are also binary search trees.

Method 1: recursion

According to the definition of binary search tree, the correctness of all subtrees can be judged by recursion (that is, whether the subsequent traversal meets the definition of binary search tree). If all subtrees are correct, this sequence is the subsequent traversal of binary search tree.

Recursive parsing:

Termination condition: when i ≥ j, it indicates that the number of nodes in this subtree is ≤ 1, and there is no need to judge the correctness, so it directly returns true;
Recursive work:
- All nodes in the left subtree interval [i, m- 1] should be < postorder [J]. And section 1 The steps of dividing the left and right subtrees ensure the correctness of the left subtree interval, so only the right subtree interval needs to be judged.
- All nodes in the right subtree interval [m,j- 1] should be > postorder[j]. The implementation method is traversal. When a node ≤ postorder[j] is encountered, it will jump out; Then p = j can be used to judge whether it is a binary search tree.
1. Divide the left and right subtrees: traverse the [i,j] interval elements traversed in sequence, find the first node larger than the root node, and the index is recorded as m. At this time, it can be divided into left subtree interval [i,m- 1], right subtree interval [m,j- 1], and root node index j.
2. Determine whether it is a binary search tree:
Return value: all subtrees need to be correct before they can be judged to be correct, so they are connected with the logical symbol &.
1. p=j: judge whether the tree is correct.
2. recur(i,m- 1): judge whether the left subtree of this tree is correct.
3. recur(m,j-1): judge whether the right subtree of this tree is correct.

Complexity analysis:

Time complexity O(N^2): each call of recur(i,j) subtracts one root node, so recursion occupies O(N); In the worst case (that is, when the tree degenerates into a linked list), each round of recursion needs to traverse all nodes of the tree and occupy O(N).
Spatial complexity O(N): in the worst case (that is, when the tree degenerates into a linked list), the recursion depth will reach N.

package com.nateshao.sword_offer.topic_26_verifyPostorder;

import java.util.Stack;

/**
 * @date Created by Shao Tongjie on 2021/11/30 14:22
 * @WeChat official account programmers
 * @Personal website www.nateshao.com cn
 * @Blog https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        int[] postorder = {1, 3, 2, 6, 5};
        int[] postorder2 = {1, 6, 3, 2, 5};// false
        int[] postorder3 = {1, 6, 3, 2, 5};// false
        System.out.println("Recursion:(postorder) = " + verifyPostorder(postorder));
        System.out.println("Recursion:(postorder2) = " + verifyPostorder(postorder2));
    }
    
    public static boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    public static boolean recur(int[] postorder, int i, int j) {
        if (i >= j) return true;
        int p = i;
        while (postorder[p] < postorder[j]) p++;
        int m = p;
        while (postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
    /**
     * Recursion: (postorder) = true
     * Recursion: (postorder2) = false
     */
}

Method 2: stack

Backward traversal order: [root node | right subtree | left subtree]. It is similar to the image of preorder traversal, that is, the order of preorder traversal is "root, left and right", and the reverse order of preorder traversal is "root, right and left".

Algorithm flow:

Initialization: monotone stack, parent node value root = + ∞ (the initial value is positive infinity, and the root node of the tree can be regarded as the left child of infinity node);
Traversing postorder in reverse order: remember that each node is ri;
1. Judgment: if RI > root, it indicates that the traversal sequence in the following order does not meet the definition of a fork search tree, and returns false directly;
2. Update parent node root: when the stack is not empty and RI < stack: peek(), loop out of the stack and assign the out of stack node to root
3. Stack: stack the current node ri;
If the traversal is completed, it indicates that the post order traversal meets the definition of binary search tree, and returns true.

package com.nateshao.sword_offer.topic_26_verifyPostorder;

import java.util.Stack;

/**
 * @date Created by Shao Tongjie on 2021/11/30 14:22
 * @WeChat official account programmers
 * @Personal website www.nateshao.com cn
 * @Blog https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description: Postorder traversal sequence of binary search tree
 */
public class Solution {
    public static void main(String[] args) {
        int[] postorder3 = {1, 6, 3, 2, 5};// false
        System.out.println("Stack:(postorder3) = " + verifyPostorder2(postorder3));
    }

    /**
     * Method 2: stack
     *
     * @param postorder
     * @return
     */
    public static boolean verifyPostorder2(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        //Initialization: monotone stack stack, parent node value root = + ∞ (the initial value is positive infinity, and the root node of the tree can be regarded as the left child of the infinity node);
        int root = Integer.MAX_VALUE;
        // Traverse postorder in reverse order: remember that each node is i
        for (int i = postorder.length - 1; i >= 0; i--) {
            // If RI > root, it indicates that the traversal sequence in the following order does not meet the definition of binary search tree, and returns false directly;
            if (postorder[i] > root) return false;
            // Update parent node root: when the stack is not empty and stack When peek() > RI, loop out of the stack and assign the out of stack node to root
            while (!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]); // Stack: stack the current node ri
        }
        return true; //When the traversal is completed, it indicates that the post order traversal meets the definition of binary search tree and returns true.
    }
    /**
     * Recursion: (postorder) = true
     * Recursion: (postorder2) = false
     * Stack: (postorder3) = false
     */
}

Reference link: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6

Added by jeff_papciak on Thu, 30 Dec 2021 22:23:06 +0200

Programming VIP

Interview question 26: post order traversal sequence of binary search tree

Sword finger Offer 26 Postorder traversal sequence of binary search tree

Method 1: recursion

Recursive parsing:

Method 2: stack

Popular Keywords