27-31

/**
 * https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
 *
 * @author Qitong!!
 * @Date 2020/7/3
 */
public class   Offer_27_       {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        //          !!
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}

/**
 * https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
 *
 * @author Qitong!!
 * @Date 2020/7/3
 */
public class   Offer_28_       {
    public boolean isSymmetric(TreeNode root) {
        //     !
        return isMirror(root, root);
    }

    private boolean isMirror(TreeNode lt, TreeNode rt) {
        if (lt == null && rt == null) return true;
        if (lt == null || rt == null) return false;
        //                ,                   ,                 
        return lt.val == rt.val && isMirror(lt.left, rt.right) && isMirror(rt.left, lt.right);
    }
}

/**
 * https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
 *
 * @author Qitong!!
 * @Date 2020/7/3
 */
public class   Offer_29_        {
    public static int[] spiralOrder(int[][] matrix) {
        if (matrix == null) return null;
        if (matrix.length == 0) return new int[]{};
        int[] res = new int[matrix.length * matrix[0].length];

        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        //res      !!
        int cur = 0;
        while (top <= bottom && left <= right) {
            //         
            for (int i = left; i <= right; i++) {
                res[cur++] = matrix[top][i];
            }
            top++;
            //         
            for (int i = top; i <= bottom; i++) {
                res[cur++] = matrix[i][right];
            }
            right--;

            if (top > bottom || left > right) break;

            //         
            for (int i = right; i >= left; i--) {
                res[cur++] = matrix[bottom][i];
            }
            bottom--;
            //         
            for (int i = bottom; i >= top; i--) {
                res[cur++] = matrix[i][left];
            }
            left++;
        }

        return res;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println(Arrays.toString(spiralOrder(matrix)));
    }
}

/**
 * https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
 *
 * @author Qitong!!
 * @Date 2020/7/3
 */
public class   Offer_30_  min     {

}

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty()) minStack.push(x);
        else {
            minStack.push(x > minStack.peek() ? minStack.peek() : x);
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}

/**
 * https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
 *
 * @author Qitong!!
 * @Date 2020/7/3
 */
public class   Offer_31_    _     {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        //     popped    
        int i = 0;
        for (int num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}