102. 二叉树的层次遍历
没啥好说的，使用队列，这里注意java也使用deque进行模拟，这里总结下deque用法：
- deque作为栈使用时：
- 添加元素：使用 push 方法将元素添加到栈的顶部。例如，deque.push(node)。
- 获取并移除元素：使用 pop 方法从栈的顶部获取并移除元素。例如，TreeNode node = deque.pop()。
- 获取但不移除元素：使用 peek 方法从栈的顶部获取但不移除元素。例如，TreeNode node = deque.peek()。
- 检查栈是否为空：使用 isEmpty 方法检查栈是否为空。例如，boolean isEmpty = deque.isEmpty()
- deque作为队列使用时：
- 添加元素：使用 add 或 offer 方法将元素添加到队列的末尾。例如，deque.add(node) 或 deque.offer(node)。
- 获取并移除元素：使用 poll 方法从队列的头部获取并移除元素。例如，TreeNode node = deque.poll()。
- 获取但不移除元素：使用 peek 方法从队列的头部获取但不移除元素。例如，TreeNode node = deque.peek()。
- 检查队列是否为空：使用 isEmpty 方法检查队列是否为空。例如，boolean isEmpty = deque.isEmpty()。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return res;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.add(root);
while(!deque.isEmpty()){
int len = deque.size();
List<Integer> res1 = new ArrayList<>();
for (int i = 0; i < len; i++){
TreeNode p = deque.peek();
res1.add(p.val);
deque.poll();
if(p.left != null){
deque.add(p.left);
}
if(p.right != null){
deque.add(p.right);
}
}
res.add(res1);
}
return res;
}
}
- while的每次循环控制的是每一层，for循环则控制的该层的每个节点。
107.二叉树的层次遍历II
就是从下往上输出，这里把层序遍历的res数组按第一维度翻转即可：
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null) {
return res;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.add(root);
while (!deque.isEmpty()) {
int len = deque.size();
List<Integer> res1 = new ArrayList<>();
for (int i = 0; i < len; i++) {
TreeNode p = deque.peek();
res1.add(p.val);
deque.poll();
if (p.left != null) {
deque.add(p.left);
}
if (p.right != null) {
deque.add(p.right);
}
}
res.add(res1);
}
Collections.reverse(res);
return res;
}
}
- Collections.reverse(res); 意思是把res翻转；
199. 二叉树的右视图
只把每一层的最后一个节点加入结果集即可。
class Solution {
private List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
if(root == null){
return res;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.add(root);
while(!deque.isEmpty()){
int len = deque.size();
for (int i = 0; i < len; i++){
TreeNode p = deque.peek();
deque.poll();
if(p.left != null){
deque.add(p.left);
}
if(p.right != null){
deque.add(p.right);
}
if(i == len - 1){
res.add(p.val);
}
}
}
return res;
}
}
- 这里注意res必须得new ArrayList()，不然会报错（和cpp不一样）
637. 二叉树的层平均值
class Solution {
private List<Double> res = new ArrayList<>();
public List<Double> averageOfLevels(TreeNode root) {
if(root == null){
return res;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.add(root);
while(!deque.isEmpty()){
int len = deque.size();
double sum = 0.0;
for (int i = 0; i < len; i++){
TreeNode p = deque.peek();
sum += p.val;
deque.poll();
if(p.left != null){
deque.add(p.left);
}
if(p.right != null){
deque.add(p.right);
}
}
res.add(sum / len);
}
return res;
}
}
429. N叉树的层次遍历
把p.left p.right换成for循环遍历children数组。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(Node root) {
if (root == null) {
return res;
}
Deque<Node> deque = new LinkedList<>();
deque.add(root);
while (!deque.isEmpty()) {
int len = deque.size();
List<Integer> res1 = new ArrayList<>();
for (int i = 0; i < len; i++) {
Node p = deque.peek();
res1.add(p.val);
deque.poll();
for (int j = 0; j < p.children.size(); j++) {
if (p.children.get(j) != null) {
deque.add(p.children.get(j));
}
}
}
res.add(res1);
}
return res;
}
}
515.在每个树行中找最大值
跟求平均值那题一样的思路：
class Solution {
private List<Integer> res = new ArrayList<>();
public List<Integer> largestValues(TreeNode root) {
if(root == null){
return res;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.add(root);
while(!deque.isEmpty()){
int len = deque.size();
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++){
TreeNode p = deque.peek();
max = Math.max(max , p.val);
deque.poll();
if(p.left != null){
deque.add(p.left);
}
if(p.right != null){
deque.add(p.right);
}
}
res.add(max);
}
return res;
}
}
- Integer.MIN_VALUE；就是取Integer中的最小值。
116.填充每个节点的下一个右侧节点指针
跟右视图那题一样，最后一个节点特殊处理，其他的练到poll后队列的头部。
class Solution {
public Node connect(Node root) {
if(root == null){
return null;
}
Deque<Node> deque = new LinkedList<>();
deque.add(root);
root.next = null;
while(!deque.isEmpty()){
int len = deque.size();
for (int i = 0; i < len; i++) {
Node p = deque.peek();
deque.poll();
p.next = deque.peek();
if(i == len - 1){
p.next = null;
}
if(p.left != null){
deque.add(p.left);
}
if(p.right != null){
deque.add(p.right);
}
}
}
return root;
}
}
117.填充每个节点的下一个右侧节点指针II
通过117.填充每个节点的下一个右侧节点指针II我们可以得到，即使不是完美二叉树也可使用上面的代码，因为在层序遍历中，以我们的上帝视角看，其实结构还是一样的，都处于同一层。
104.二叉树的最大深度
层序遍历：用一个depth变量记录遍历的层数：
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int depth = 0;
Deque<TreeNode> deque = new LinkedList<>();
deque.add(root);
while (!deque.isEmpty()) {
int len = deque.size();
depth++;
for (int i = 0; i < len; i++) {
TreeNode p = deque.peek();
deque.poll();
if (p.left != null) {
deque.add(p.left);
}
if (p.right != null) {
deque.add(p.right);
}
}
}
return depth;
}
}
111.二叉树的最小深度
一碰到叶子结点就停止输出：
class Solution {
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
int depth = 0;
Deque<TreeNode> deque = new LinkedList<>();
deque.add(root);
while(!deque.isEmpty()){
int len = deque.size();
depth++;
List<Integer> res1 = new ArrayList<>();
for (int i = 0; i < len; i++){
TreeNode p = deque.peek();
deque.poll();
if(p.left == null && p.right == null){
return depth;
}
if(p.left != null){
deque.add(p.left);
}
if(p.right != null){
deque.add(p.right);
}
}
}
return depth;
}
}
226.翻转二叉树
递归法：
class Solution {
private TreeNode traversal(TreeNode node){
if(node == null){
return null;
}
TreeNode left = traversal(node.left);
TreeNode right = traversal(node.right);
node.left = right;
node.right = left;
return node;
}
public TreeNode invertTree(TreeNode root) {
traversal(root);
return root;
}
}
迭代法：
public TreeNode invertTree(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
if(root == null){
return null;
}
deque.push(root);
while(!deque.isEmpty()){
TreeNode p = deque.peek();
deque.pop();
TreeNode tmp = p.right;
p.right = p.left;
p.left = tmp;
if(p.right != null){
deque.push(p.right);
}
if(p.left != null){
deque.push(p.left);
}
}
return root;
}
110.平衡二叉树
- 本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
- 思路：递归求两个子树高度，一旦不满足平衡了，就把该节点的高度设置为-1；
- 一旦子树中有-1，那么本身肯定不是二叉平衡树了，直接返回-1；
- 如果还是，更新高度为Math.max(left, right) + 1;
class Solution {
private int getHeight(TreeNode node){
if(node =