LeetCode-0525

102. 二叉树的层序遍历（中等）

思路：使用hash记录深度

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if(root==null)return new ArrayList<>();Map<TreeNode,Integer> deep = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();int d = deepth(root);List<List<Integer>> res = new ArrayList<>();for(int i=0;i<d;i++){res.add(new ArrayList<>());}queue.offer(root);deep.put(root,0);while(!queue.isEmpty()){TreeNode cur = queue.poll();int dp = deep.get(cur);res.get(dp).add(cur.val);if(cur.left!=null){queue.offer(cur.left);deep.put(cur.left,dp+1);}if(cur.right!=null){queue.offer(cur.right);deep.put(cur.right,dp+1);}}return res;}public int deepth(TreeNode root){if(root==null)return 0;return Math.max(deepth(root.left),deepth(root.right))+1;}
}

107. 二叉树的层序遍历 II(中等)

思路：相比刚才的解答，只需要将数组的赋值改一下即可

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {if(root==null)return new ArrayList<>();Map<TreeNode,Integer> deep = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();int d = deepth(root);List<List<Integer>> res = new ArrayList<>();for(int i=0;i<d;i++){res.add(new ArrayList<>());}queue.offer(root);deep.put(root,0);while(!queue.isEmpty()){TreeNode cur = queue.poll();int dp = deep.get(cur);res.get(d-dp-1).add(cur.val);if(cur.left!=null){queue.offer(cur.left);deep.put(cur.left,dp+1);}if(cur.right!=null){queue.offer(cur.right);deep.put(cur.right,dp+1);}}return res;}public int deepth(TreeNode root){if(root==null)return 0;return Math.max(deepth(root.left),deepth(root.right))+1;}
}

199. 二叉树的右视图(中等)

思路：一开始想一直找最右子，然后发现有可能左子树比右子树高，这样就不对了。之后还是在层序遍历的模版上微调一下

class Solution {public List<Integer> rightSideView(TreeNode root) {if(root==null)return new ArrayList<>();Map<TreeNode,Integer> deep = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();int d = deepth(root);List<List<Integer>> res = new ArrayList<>();List<Integer> ans = new ArrayList<>();for(int i=0;i<d;i++){res.add(new ArrayList<>());}queue.offer(root);deep.put(root,0);while(!queue.isEmpty()){TreeNode cur = queue.poll();int dp = deep.get(cur);res.get(dp).add(cur.val);if(cur.left!=null){queue.offer(cur.left);deep.put(cur.left,dp+1);}if(cur.right!=null){queue.offer(cur.right);deep.put(cur.right,dp+1);}}for(int i=0;i<d;i++){List<Integer> tp = res.get(i);ans.add(tp.get(tp.size()-1));}return ans;}public int deepth(TreeNode root){if(root==null)return 0;return Math.max(deepth(root.left),deepth(root.right))+1;}
}

637. 二叉树的层平均值(简单)

思路：还是之前的模版

官方题解里面，可以在while里面for遍历队列进行处理，每一次遍历，都是同一层的元素，极好的解决了深度问题

class Solution {public List<Double> averageOfLevels(TreeNode root) {if(root==null)return new ArrayList<>();Map<TreeNode,Integer> deep = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();int d = deepth(root);List<List<Integer>> res = new ArrayList<>();List<Double> ans = new ArrayList<>();for(int i=0;i<d;i++){res.add(new ArrayList<>());}queue.offer(root);deep.put(root,0);while(!queue.isEmpty()){TreeNode cur = queue.poll();int dp = deep.get(cur);res.get(dp).add(cur.val);if(cur.left!=null){queue.offer(cur.left);deep.put(cur.left,dp+1);}if(cur.right!=null){queue.offer(cur.right);deep.put(cur.right,dp+1);}}for(int i=0;i<d;i++){List<Integer> tp = res.get(i);double sum = 0;for(int j=0;j<tp.size();j++){sum+=tp.get(j);}ans.add(sum/tp.size());}return ans;}public int deepth(TreeNode root){if(root==null)return 0;return Math.max(deepth(root.left),deepth(root.right))+1;}
}

429. N 叉树的层序遍历（中等）

思路：使用上一题官方题解的办法

class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> res  = new ArrayList<>();if(root == null) return res;Queue<Node> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){List<Integer> level = new ArrayList<>();int size = queue.size();	//	这里一定要先取出size，不然中间会增加for(int i=0;i<size;i++){Node cur = queue.poll();level.add(cur.val);for(int j=0;j<cur.children.size();j++){queue.offer(cur.children.get(j));}}res.add(level);}return res;}
}

515. 在每个树行中找最大值(中等)

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> res  = new ArrayList<>();if(root == null) return res;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int max = queue.peek().val;int size = queue.size();for(int i=0;i<size;i++){TreeNode cur = queue.poll();if(cur.val>max)max = cur.val;if(cur.left!=null)queue.offer(cur.left);if(cur.right!=null)queue.offer(cur.right);}res.add(max);}return res;}
}

116. 填充每个节点的下一个右侧节点指针

class Solution {public Node connect(Node root) {if(root==null)return root;Queue<Node> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int size = queue.size();Node last = null;for(int i=0;i<size;i++){Node cur = queue.poll();if(last!=null)last.next = cur;last = cur;if(cur.left!=null)queue.offer(cur.left);if(cur.right!=null)queue.offer(cur.right);}}return root;}
}

117. 填充每个节点的下一个右侧节点指针 II(中等)

完全同上

104. 二叉树的最大深度(简单)

class Solution {public int maxDepth(TreeNode root) {if(root==null)return 0;return Math.max(maxDepth(root.left),maxDepth(root.right))+1;}
}

111. 二叉树的最小深度(简单)

class Solution {public int minDepth(TreeNode root) {if(root==null)return 0;if(root.left==null||root.right==null)return Math.max(minDepth(root.left),minDepth(root.right))+1;return Math.min(minDepth(root.left),minDepth(root.right))+1;}}