[TOC]

二叉树

671.二叉树中第二小的节点

• 利用题目条件root.val = min(root.left.val, root.right.val) 得知第二小的数即为比 root.val 大的第一个数，因为 root.val 是二叉树中最小的节点。

  public int findSecondMinimumValue(TreeNode root) {
      return findBigger(root, root.val);
  }
  
  public int findBigger(TreeNode root, int value) {
      if (root == null) {
          return -1;
      }
      if (root.val > value) {
          return root.val;
      }
      int left = findBigger(root.left, value);
      int right = findBigger(root.right, value);
      if (left > 0 && right > 0) {
          return Math.min(left, right);
      }
      return Math.max(left, right);
  }
  

1104.二叉树寻路

• 利用完全二叉树的根节点和叶子节点下标的对应关系，往上计算下标。

• 偶数行通过当前行的起始节点下标和最后一个节点的下标计算偏移。

  public List<Integer> pathInZigZagTree(int label) {
      int row = (int) (Math.log(label) / Math.log(2)) + 1;
      List<Integer> res = new ArrayList<>();
      if ((row & 0x1) == 0) {
          label = (1 << (row - 1)) + ((1 << row) - 1) - label;
      }
      while (row > 0) {
          res.add((row & 0x1) == 0 ? (1 << (row - 1)) + ((1 << row) - 1) - label : label);
          label = (label >> 1);
          row--;
      }
      Collections.reverse(res);
      return res;
  }
  

987.二叉树的垂序遍历

• 自定义排序 + DFS

  TreeMap<Integer, LinkedList<int[]>> res = new TreeMap<>();
  public List<List<Integer>> verticalTraversal(TreeNode root) {
      dfs(root, 0, 0);
      List<List<Integer>> result = new ArrayList<>();
      for (LinkedList<int[]> tmp : res.values()) {
          Collections.sort(tmp, (o1, o2) -> {
              if (o1[0] == o2[0]) {
                  return o1[1] - o2[1];
              }
              return o1[0] - o2[0];
          });
          List<Integer> level = new ArrayList<>(tmp.size());
          for (int[] val : tmp) {
              level.add(val[1]);
          }
          result.add(level);
      }
      return result;
  }
  
  void dfs(TreeNode root, int row, int col) {
      if (root == null) {
          return;
      }
      LinkedList<int[]> curr = res.getOrDefault(col, new LinkedList<>());
      curr.addLast(new int[]{row, root.val});
      res.put(col, curr);
      dfs(root.left, row + 1, col - 1);
      dfs(root.right, row + 1, col + 1);
  }
  

二叉搜索树

98.验证二叉搜索树

• <font color = red>误区：将 root.val 与 left.val 和 right.val 进行比较。</font>

• 需要比较左子树最大值和右子树最小值，然后递归验证左子树和右子树。

  public boolean isValidBST(TreeNode root) {
    if (root == null) {
      return true;
    }
    int maxLeft = Integer.MIN_VALUE;
    TreeNode left = root.left;
    while (left != null) {
      maxLeft = left.val;
      left = left.right;
    }
    int minRight = Integer.MAX_VALUE;
    TreeNode right = root.right;
    while (right != null) {
      minRight = right.val;
      right = right.left;
    }
    return (root.left == null || root.val > maxLeft) && (root.right == null || root.val < minRight) && isValidBST(root.left) && isValidBST(root.right);
  }
  

173.二叉搜索树迭代器

• 题目要求O(h)空间复杂度，直接想到深度优先搜索，使用栈存储节点，通过中序遍历二叉树。

  class BSTIterator {
    Stack<TreeNode> queue = new Stack<>();
    public BSTIterator(TreeNode root) {
      while (root != null) {
        queue.push(root);
        root = root.left;
      }
    }
  
    public int next() {
      if (queue.isEmpty()) {
        return Integer.MIN_VALUE;
      }
      TreeNode currNode = queue.pop();
      if (currNode.right != null) {
        TreeNode node = currNode.right;
        while (node != null) {
          queue.push(node);
          node = node.left;
        }
      }
      return currNode.val;
    }
  
    public boolean hasNext() {
      return !queue.isEmpty();
    }
  }