LeetCode(46) -- 993,

P993. Cousins in Binary Tree (Easy)

一个二叉树，根节点的深度为0。如果两个节点深度相同，但父节点不同，我们就叫它们cousin。

我的思路

先算出两个节点的深度，然后再判断它们的父节点是否相同。

我的代码

public class E_993_CousinsinBinaryTree {
    public boolean isCousins(TreeNode root, int x, int y) {
        int depthX = findDepth(root, 0, x);
        int depthY = findDepth(root, 0, y);
        return depthX == depthY && !sameParent(root, x, y);
    }

    private int findDepth(TreeNode node, int currentDepth, int target) {
        if (node.val == target) {
            return currentDepth;
        }
        if (node.left != null) {
            int depthLeft = findDepth(node.left, currentDepth + 1, target);
            if (depthLeft != -1) {
                return depthLeft;
            }
        }
        if (node.right != null) {
            int depthRight = findDepth(node.right, currentDepth + 1, target);
            if (depthRight != -1) {
                return depthRight;
            }
        }
        return -1;
    }

    private boolean sameParent(TreeNode root, int x, int y) {
        if (root == null) {
            return false;
        }
        if (root.left != null && root.right != null) {
            if ((root.left.val == x && root.right.val == y) ||
            (root.left.val == y && root.right.val == x)) {
                return true;
            }
        }
        return sameParent(root.left, x, y) || sameParent(root.right, x, y);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(5);
        root.right.left.left = new TreeNode(4);
        root.right.left.left.right = new TreeNode(6);
        boolean cousins = new E_993_CousinsinBinaryTree().isCousins(root, 5, 3);
        System.out.println("cousins = " + cousins);
    }
}

100%

最优解

class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        if (root == null || x == y) {
            return false;
        }
        TreeNode xParent = new TreeNode(0), yParent = new TreeNode(0);
        int xLevel = getLevelOf(root, x, xParent);
        int yLevel = getLevelOf(root, y, yParent);
        return xLevel == yLevel && xParent.val != yParent.val;
    }

    private Integer getLevelOf(TreeNode node, int value, TreeNode parent) {
        if (node == null) {
            return null;
        }

        if (node.val == value) {
            return 0;
        }

        Integer left = getLevelOf(node.left, value, parent);
        if (left != null) {
            if (parent.val == 0) {
                parent.val = node.val;
            }
            return left + 1;
        }

        Integer right = getLevelOf(node.right, value, parent);
        if (right != null) {
            if (parent.val == 0) {
                parent.val = node.val;
            }
            return right + 1;
        }
        return null;
    }
}

P994. Rotting Oranges (Easy)

烂橘子问题：在一个矩阵中，2表示烂橘子，1表示好橘子，0表示该位置什么都没有。每过一天，所有烂橘子上下左右四个方向的好橘子也会烂掉。问经过几天之后，所有的橘子全烂掉？

我的思路

BFS，先全扫一遍，看看哪些橘子烂掉了，就把它们周边的好橘子的坐标放到一个list里。然后只要这个list不为空，就先把它们所有数变成2，再检查已经在list中的每一个坐标周边是否有好橘子，如果有，就重新放到list里。这里需要注意，遍历的次数，以初始的size为准，后来再加进去的，暂时先不管。（因为要计算天数，每一轮都是一天）

我的代码

public class E_994_RottingOranges {
    LinkedList<IntPair> list = new LinkedList<>();
    public int orangesRotting(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) {
                    checkAndAddToQueue(i, j, grid);
                }
            }
        }
        int count = 0;
        while (list.size() != 0) {
            count++;
            int size = list.size();
            for (IntPair pair : list) {
                grid[pair.x][pair.y] = 2;
            }
            for (int i = 0; i < size; i++) {
                IntPair pair = list.remove();
                checkAndAddToQueue(pair.x, pair.y, grid);
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return count;
    }

    private void checkAndAddToQueue(int i, int j, int[][] grid) {
        if (i > 0 && grid[i - 1][j] == 1) {
            list.add(new IntPair(i - 1, j));
        }
        if (i < grid.length - 1 && grid[i + 1][j] == 1) {
            list.add(new IntPair(i + 1, j));
        }
        if (j > 0 && grid[i][j - 1] == 1) {
            list.add(new IntPair(i, j - 1));
        }
        if (j < grid[i].length - 1 && grid[i][j + 1] == 1) {
            list.add(new IntPair(i, j + 1));
        }
    }
}

 class IntPair {
    int x;
    int y;
    IntPair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

86%

最优解

class Solution
{
  //private final static int EMPTY = 0;
  private final static int FRESH = 1;
  private final static int ROTTEN = 2;

  public int orangesRotting(int[][] grid)
  {
    final int n = grid.length;
    final int m = grid[0].length;

    int freshCount = 0;

    Queue<Integer> queue = new LinkedList<>();
    for (int i=0; i<n; i++)
      for (int j=0; j<m; j++)
      {
        if (grid[i][j] == FRESH)
          freshCount++;
        else if (grid[i][j] == ROTTEN)
          queue.add(i*m +j);
      }

    if (freshCount == 0) return 0;

    int minuts = 2;
    while (!queue.isEmpty())
    {
      int code = queue.remove();
      int i = code / m;
      int j = code % m;
      minuts = grid[i][j] + 1;
      int k = i-1;
      if ((k > -1) && (grid[k][j] == FRESH))
      {
        grid[k][j] = minuts;
        freshCount--;
        queue.add((k)*m +j);
      }

      k = i+1;
      if ((k < n) && (grid[k][j] == FRESH))
      {
        grid[k][j] = minuts;
        freshCount--;
        queue.add((k)*m +j);
      }

      k = j-1;
      if ((k > -1) && (grid[i][k] == FRESH))
      {
        grid[i][k] = minuts;
        freshCount--;
        queue.add((i)*m +k);
      }

      k = j+1;
      if ((k < m) && (grid[i][k] == FRESH))
      {
        grid[i][k] = minuts;
        freshCount--;
        queue.add((i)*m +k);
      }
    }

    return (freshCount > 0) ? -1 : minuts - 3;
  }
}

用i * 列数 + j，就能算出矩阵里的序号，不需要像我一样再写一个pair的类来记录。 这个代码的意思是，因为本身这个矩阵里0，1，2都有其特殊含义了，但是作者又想用矩阵里的数来代表过了几分钟，于是就把minute初始化成2，最后再减3。