662. 二叉树最大宽度

思路：深搜时用哈希表记录每层的信息

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     Map<Integer, Integer> map = new HashMap<>();
  18.     int max;
  19.     public int widthOfBinaryTree(TreeNode root) {
  20.         dfs(root, 0, 0);
  21.         return max;
  22.     }
  24.     void dfs(TreeNode u, int d, int x) {
  25.         if (u == null) return;
  26.         if (!map.containsKey(d)) {
  27.             map.put(d, x);
  28.             max = Math.max(max, 1);
  29.         } else {
  30.             max = Math.max(max, x - map.get(d) + 1);
  31.         }
  33.         dfs(u.left, d + 1, x * 2);
  34.         dfs(u.right, d + 1, x * 2 + 1);
  35.     }
  36. }

779. 第K个语法符号

抽象成树形结构
每个节点的值与左节点的值相同，与右节点的值相反
从目标节点向上倒推至第一层

  1. class Solution {
  2.     public int kthGrammar(int n, int k) {
  3.         int v = 1;
  4.         while (n > 1) {
  5.             int p = (k + 1) / 2;
  6.             if (k % 2 == 0)
  7.                 v ^= 1;
  8.             k = p;
  9.             n--;
  10.         }
  11.         return v == 0 ? 1 : 0;
  12.     }
  13. }