Leetcode sword finger offer brush questions - day 20

Leetcode The finger of the sword Offer How to brush questions ：

Leetcode The finger of the sword Offer Brush problem - Learning plan directory _DEGv587 The blog of -CSDN Blog

The finger of the sword Offer 07. Reconstruction of binary tree  

Topic information ： The results of preorder traversal and inorder traversal do not contain duplicate numbers

solution ： Divide and conquer thoughts

class Solution {
    int[] preorder;// Preserved preorder traversal 
    HashMap<Integer, Integer> map = new HashMap<>();// Tag middle order traversal 

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; ++i) {
            map.put(inorder[i], i);
        }
        return func(0, 0, inorder.length - 1);
    }

    private TreeNode func(int root, int left, int right) {
        if (left > right) return null;
        TreeNode node = new TreeNode(preorder[root]);// Establish root node 
        int i = map.get(preorder[root]);// Partition root node , Left and right subtrees 

        node.left = func(root + 1, left, i - 1);// Left subtree recursion 
        node.right = func(root + i - left + 1, i + 1, right);// Right subtree recursion 
        return node;
    }
}

The finger of the sword Offer 16. Integer power of value

solution ： Fast power

Stepwise decomposition

Even transformation , One more odd number for processing

2^10 = (2^5) * (2^5) = (4^2) * (4^2) * 4 = 16 * 16 * 4

class Solution {
    public double myPow(double x, int n) {
        if (x == 0) return 0;
        long b = n;// To prevent cross-border 
        double ret = 1.0;
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }

        while (b > 0) {
            if ((b & 1) == 1) {
                // Deal with odd numbers 
                ret *= x;
            }
            x *= x;
            b >>= 1;
        }

        return ret;
    }
}

The finger of the sword Offer 33. The post order traversal sequence of binary search tree

Solution 1 ： Recursive divide and conquer

Ergodic sequence ergodic [i, j] Interval elements , seek The first is larger than the root node The node of , The index is marked as m

postorder[j] Is the root node

Left subtree interval [i, m - 1] All nodes in the should < postorder[j]

Right subtree interval [m, j-1] All nodes in the should > postorder[j]

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

    private boolean verifyHelp(int[] postorder, int i, int j) {
        if (i >= j) return true;

        int p = i;
        while (postorder[p] < postorder[j]) {
            // If it is smaller than the root node, continue to walk backwards 
            p++;
        }
        // Encounter the first value greater than the root node , Record as m
        int m = p;
        while (postorder[p] > postorder[j]) {
            // If it is larger than the root node, continue to walk backwards 
            p++;
        }

        // Recursively divide and conquer left subtree and right subtree 
        return p == j && verifyHelp(postorder, i, m - 1) && verifyHelp(postorder, m, j - 1);
    }
}

Solution 2 ： Auxiliary monotone stack

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; --i) {
            // If the current node is larger than the root node , Then return directly false
            if (postorder[i] > root) return false;
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                // Find the parent node of the current node 
                root = stack.pop();
            }
            stack.add(postorder[i]);
        }

        return true;
    }
}