662. 二叉树最大宽度
难度中等给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
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 public int widthOfBinaryTree(TreeNode root) {
18 Queue<TreeNode> q=new LinkedList<>();
19 root.val=1;
20 q.offer(root);
21 int ans=0;
22 while (!q.isEmpty()){
23 int size=q.size();
24 int l=-1;
25 int r=-1;
26 for (int i=0;i<size;i++){
27 TreeNode node=q.poll();
28 if (i==0) l=node.val;
29 if (i==size-1) r=node.val;
30 if (node.left!=null){
31 node.left.val=node.val*2;
32 q.offer(node.left);
33 }
34 if (node.right!=null){
35 node.right.val=node.val*2+1;
36 q.offer(node.right);
37 }
38 }
39 ans=Math.max(ans,r-l+1);
40 }
41 return ans;
42 }
43 }
思路：记录当前节点的位置（个数，左子树就是根的两倍，右子树就是根的两倍多一，层序遍历直接看最前面和最后面的宽度。
剑指 Offer II 064. 神奇的字典
难度中等设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。
实现 MagicDictionary 类：
MagicDictionary()初始化对象void buildDict(String[] dictionary)使用字符串数组dictionary设定该数据结构，dictionary中的字符串互不相同bool search(String searchWord)给定一个字符串searchWord，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回true；否则，返回false。
1 class MagicDictionary {
2 Trie root;
3 /** Initialize your data structure here. */
4 public MagicDictionary() {
5 root=new Trie();
6 }
7
8 public void buildDict(String[] dictionary) {
9 for (String s:dictionary){
10 Trie head=root;
11 for (int i=0;i<s.length();i++){
12 int index=s.charAt(i)-'a';
13 if (head.children[index]==null){
14 head.children[index]=new Trie();
15 }
16 head=head.children[index];
17 }
18 head.isWord=true;
19 }
20 }
21
22 public boolean search(String searchWord) {
23 return dfs(searchWord,root,0,false);
24 }
25
26 public boolean dfs(String word,Trie root,int index,boolean modified){
27 if (index==word.length()) return root.isWord&&modified;
28 int idx=word.charAt(index)-'a';
29 if (root.children[idx]!=null){
30 if (dfs(word,root.children[idx],index+1,modified)){
31 return true;
32 }
33 }
34 if (!modified){
35 for (int i=0;i<26;i++){
36 if (i!=idx&&root.children[i]!=null){
37 if (dfs(word,root.children[i],index+1,true)){
38 return true;
39 }
40 }
41 }
42 }
43 return false;
44 }
45 }
46
47 class Trie{
48 boolean isWord;
49 Trie[] children;
50 Trie(){
51 isWord=false;
52 children=new Trie[26];
53 }
54 }
55
56 /**
57 * Your MagicDictionary object will be instantiated and called as such:
58 * MagicDictionary obj = new MagicDictionary();
59 * obj.buildDict(dictionary);
60 * boolean param_2 = obj.search(searchWord);
61 */
思路：字典树记录单词，dfs搜索是否可行。
标签：TreeNode,dictionary,val,offer,int,层序,dfs,单词,root From： https://www.cnblogs.com/benbicao/p/16630318.html