This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

Topic describes

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 Example 1: Input: [1,6,3,2,5] Output: false Example 2: Input: [1,3,2,6,5] Output: True source: LeetCode Link: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • Today’s problem of the day is the application of knowledge in searching binary trees. Binary search trees have the following properties:
  1. If the left subtree of any node is not empty, the value of all nodes in the left subtree is not greater than the value of its root.
  2. If the right subtree of any node is not empty, the value of all nodes in the right subtree is not less than the value of its root node.
  3. The left and right subtrees of any node are binary search trees respectively.
  • According to the problem stem, we need to determine whether the array given is the result of a sequential traversal of a binary search tree. We can only guarantee the result of subsequent traversal:
  1. The value of all elements of the left subtree is < the value of the root node
  2. Values of all elements in the right subtree > values of the root node
  • Since they gave us the back-order traversal order, we can get the following code.

Through the code

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        int n = postorder.length;
        return helper(postorder, 0, n - 1);
    }

    public boolean helper(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 && helper(postorder, i, m - 1) && helper(postorder, m, j - 1); }}Copy the code

conclusion

  • Binomial tree common investigation topics and the construction of binomial tree, the depth of binomial tree. This kind of topic needs more practice, more summary, in order to better master.
  • Adhere to the algorithm of the day, come on!