算法训练营Day15(二叉树)

层序遍历 

102. 二叉树的层序遍历 - 力扣（LeetCode）

核心理解size存放的是当前这一层的，poll出来的时候，孩子可以放进去。但是这一层做的时候是通过szie判断这一层的，比如size==1，那就放到subRes，此时孩子节点也进去了，但是是size控制这一层的结果，加入res，进入下一循环。

（核心就是：弹出去一个就把孩子加到队列，通过size判断是这一层要弹出哪些。）

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();Deque<TreeNode> deque = new LinkedList<>();if(root!=null){deque.add(root);}while (!deque.isEmpty()){int size = deque.size();List<Integer> subRes = new ArrayList<>();while (size-->0){TreeNode child = deque.poll();subRes.add(child.val);if(child.left!=null){deque.add(child.left);}if(child.right!=null){deque.add(child.right);}}res.add(subRes);}return res;}
}

107. 二叉树的层序遍历 II - 力扣（LeetCode）

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> res = new ArrayList<>();Deque<TreeNode> deque = new ArrayDeque<>();if(root!=null){deque.add(root);}while(!deque.isEmpty()){int size = deque.size();List<Integer> subRes = new ArrayList<>();while (size-->0){TreeNode child = deque.poll();subRes.add(child.val);if(child.left!=null){deque.add(child.left);}if(child.right!=null){deque.add(child.right);}}res.add(subRes);}List<List<Integer>> bottomRes = new ArrayList<>();for (int i = res.size()-1; i >= 0; i--) {bottomRes.add(res.get(i));}return bottomRes;}
}

199. 二叉树的右视图 - 力扣（LeetCode）

就是在每一层遍历的时候，size=0的时候加结果里面，（1的时候符合条件，但是有个--操作，所以最后一个判断的时候是0）

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> deque = new LinkedList<>();if(root!=null){deque.add(root);}while (!deque.isEmpty()){int size = deque.size();while (size-->0){TreeNode child = deque.poll();if(size==0){res.add(child.val);}if(child.left!=null){deque.add(child.left);}if(child.right!=null){deque.add(child.right);}}}return res;}
}

637. 二叉树的层平均值 - 力扣（LeetCode）

public List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();Deque<TreeNode> deque = new LinkedList<>();if(root!=null){deque.add(root);}while (!deque.isEmpty()){int size = deque.size();double sum = 0.0;//因为用到szie，不采用while循环方式for (int i = 0; i < size; i++) {TreeNode poll = deque.poll();sum += poll.val;if (poll.left != null) {deque.add(poll.left);}if (poll.right != null) {deque.add(poll.right);}}res.add(sum / size);}return res;}

226.翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

class Solution {public TreeNode invertTree(TreeNode root) {if(root==null){return null;}swapNode(root);invertTree(root.left);invertTree(root.right);return root;}private void swapNode(TreeNode root) {TreeNode temp = root.left;root.left=root.right;root.right=temp;}
}

101. 对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

class Solution {public boolean isSymmetric(TreeNode root) {return symmetric(root.left,root.right);}private boolean symmetric(TreeNode left, TreeNode right) {if (left == null && right != null) {return false;}if (left != null && right == null) {return false;}if (left == null && right == null) {return true;}if (left.val != right.val) {return false;}boolean out = symmetric(left.left,right.right);boolean in = symmetric(left.right,right.left);return out && in;}
}

二刷回顾

补充剩下的简单题

代码随想录 (programmercarl.com)

二刷补充完层序遍历剩下的题目，以及101用层序和栈的方法解决，残缺版本如下：

public boolean isSymmetric1(TreeNode root) {Deque<TreeNode> deque = new LinkedList<>();if(root!=null){deque.add(root);}while (!deque.isEmpty()){int size = deque.size();if(size==1){deque.add(root.left);deque.add(root.right);continue;}Deque<TreeNode> stack = new LinkedList<>();for (int i = 0; i < size / 2; i++) {TreeNode poll = deque.poll();push(poll,deque);stack.add(poll);}for (int i = size/2; i < size; i++) {TreeNode poll = deque.poll();if(stack.pop()!=poll){return false;}push(poll,deque);}}return true;}private void push(TreeNode child,Deque<TreeNode> deque){if(child.left!=null) {deque.add(child.left);}else {deque.add(null);}if(child.right!=null){deque.add(child.right);}else {deque.add(null);}}