Stack

刷题最主要要理解思想，如何利用抽象的数据结构来解决这个问题。

算法的本质就是你通过一系列的运算能够获得题目要求想要的答案，所以思考这一系列步骤是可以通过抽象的数据结构或者之前的pattern来完成的，而好记性不如烂笔头子，所以把这些思想记录下来还是非常有用的，之后可以时不时翻出来看一下。

而算法的改进也是先通过最基础的本办法一点点改进过来的。所以不必懊恼自己没能一开始就想出最优解。

stack 的问题也有很多种， 今天又复习了一下inorder successor和walls and gates，发现自己既是了解了思想之后在实际implementation的时候还是不能实现这个算法。就说明自己的工程能力还是很弱，需要练习。

inorder successor 这道题我主要卡在了如何利用stack来实现自己的想法这上面，我一开始想的是直接push root 进stack然后便利到最左边，然后pop，这样就可以开始对比两个的数值了。（当前node和target的数值）

但这样想有个问题，如果目标的node是在这棵树上最右边的地方，那么你如何找到它inorder successor？所以正确的方式是在while (!stack.isEmpty()) 这个循环里面再嵌套一个判断条件，这样你每次pop的时候就是前一个node的inorder successor，因为你stack push的顺序就是按照inorder 的顺序push的，pop的时候就等于pop了它inorder successor。

看一下下面的代码可能更清晰一点，精髓就在于他在结尾的时候更新了inorder的value，这样你下一次循环pop的时候一定是它的inorder successor。

        int inorder = Integer.MAX_VALUE;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        while (!stack.isEmpty() || root != null) {
            // go to most left child node
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (inorder == p.val) {
                return root;
            }
            inorder = root.val;
            root = root.right;
        }
        return null;

walls and gates这道题我也是在实现的时候出了问题，其实思想就是BFS，没什么好说的，但是实现的时候就遇到麻烦了。

自己以为用两个for loop循环，找到一个gates的时候把坐标加入队列，然后把周围空房间的坐标更新后也加入队列就行了。

但是这样结果就是你的答案并不是最优解，就是说题目要求空房间的坐标应该是离最近的gate的距离，那么你这样2个for loop找到一个gate就加入队列的用法实际上不能保证每个空房间的值都是离最近的gate的距离，所以这样implement是有问题的。

正确的做法应该是在两个for loop的时候先把所有的gate的坐标加入队列，然后while(!q.isEmpty()) 在把每个gate附近空房间的值更新并加入队列，这样你就保证了你会先把每个gate附近的空房间的值更新（因为用了队列这个数据结构），所以保证了能够满足题目的要求。

下面是代码：

class wallsAndGates {
    int[][] dir = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int INF = Integer.MAX_VALUE;
    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length;
        if (m == 0) return;
        int n = rooms[0].length;
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    q.add(new int[] {i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int[] gate = q.poll();
            int pos_x = gate[0];
            int pos_y = gate[1];
            for (int k = 0; k < 4; k++) {
                int x = pos_x + dir[k][0];
                int y = pos_y + dir[k][1];
                if (x < 0 || x > m - 1 || y < 0 || y > n - 1) {
                    continue;
                } else {
                    if (rooms[x][y] == INF) {
                        rooms[x][y] = rooms[pos_x][pos_y] + 1;
                        q.add(new int[] {x, y});
                    }
                }
            }
        }
    }
}