[TOC]

二叉樹

671.二叉樹中第二小的節(jié)點(diǎn)

• 利用題目條件root.val = min(root.left.val, root.right.val) 得知第二小的數(shù)即為比 root.val 大的第一個(gè)數(shù)，因?yàn)?root.val 是二叉樹中最小的節(jié)點(diǎn)。

  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.二叉樹尋路

• 利用完全二叉樹的根節(jié)點(diǎn)和葉子節(jié)點(diǎn)下標(biāo)的對(duì)應(yīng)關(guān)系，往上計(jì)算下標(biāo)。

• 偶數(shù)行通過當(dāng)前行的起始節(jié)點(diǎn)下標(biāo)和最后一個(gè)節(jié)點(diǎn)的下標(biāo)計(jì)算偏移。

  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.驗(yàn)證二叉搜索樹

• <font color = red>誤區(qū)：將 root.val 與 left.val 和 right.val 進(jìn)行比較。</font>

• 需要比較左子樹最大值和右子樹最小值，然后遞歸驗(yàn)證左子樹和右子樹。

  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)空間復(fù)雜度，直接想到深度優(yōu)先搜索，使用棧存儲(chǔ)節(jié)點(diǎn)，通過中序遍歷二叉樹。

  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();
    }
  }