文章目录
快速复习
二叉树的右视图
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer>ans=new ArrayList<>();
if(root==null){
return ans;
}
Deque<TreeNode> queue=new LinkedList<>();
queue.addLast(root);
while (!queue.isEmpty()){
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.removeFirst();
if(i==size-1){
ans.add(node.val);
}
if(node.left!=null){
queue.addLast(node.left);
}
if(node.right!=null){
queue.addLast(node.right);
}
}
}
return ans;
}
}
二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans=new ArrayList<>();
if(root==null)
return ans;
Deque<TreeNode> queue=new LinkedList<>();
queue.addLast(root);
while (!queue.isEmpty()){
int size = queue.size();
List<Integer> tmp=new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode curNode = queue.removeFirst();
tmp.add(curNode.val);
if(curNode.left!=null)
queue.addLast(curNode.left);
if(curNode.right!=null)
queue.addLast(curNode.right);
}
ans.add(tmp);
//ans.add(0,tmp);这样就把层次反过来了。
}
return ans;
}
}
层序遍历保存成链表
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
ListNode[]ans;
public ListNode[] listOfDepth(TreeNode root) {
List<ListNode>tempList=new ArrayList<>();
if (root==null){
return ans;
}
Deque<TreeNode>queue=new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
ListNode head=null;
ListNode p=null;
for (int i = 0; i < size; i++) {
TreeNode poll = queue.poll();
if(i==0){
head = new ListNode(poll.val);
p=head;
}else {
ListNode temp=new ListNode(poll.val);
p.next=temp;
p=temp;
}
if(poll.left!=null){
queue.offer(poll.left);
}
if(poll.right!=null){
queue.offer(poll.right);
}
}
tempList.add(head);
}
ans=new ListNode[tempList.size()];
int idx=0;
for (ListNode listNode : tempList) {
ans[idx++]=listNode;
}
return ans;
}
}
二叉树的锯齿形层序遍历
添加链接描述
相比上题需要记录当前层level
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans=new ArrayList<>();
if(root==null){
return ans;
}
Deque<TreeNode>queue=new LinkedList<>();
queue.addLast(root);
int level=0; //多了一个这
while (!queue.isEmpty()){
int size = queue.size();
List<Integer> temp=new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.removeFirst();
temp.add(cur.val);
if(cur.left!=null){
queue.addLast(cur.left);
}
if(cur.right!=null){
queue.addLast(cur.right);
}
}
level++;
if(level%2==1){ //设置根为1层
ans.add(temp);
}else {
Collections.reverse(temp);
ans.add(temp);
}
}
return ans;
}
}
二叉树的最小深度
首先本题dfs和bfs都可以，但是bfs要更高效，面试肯定写bfs。
dfs
class Solution {
int minDepth=Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
dfs(root,1);
return minDepth;
}
private void dfs(TreeNode root, int depth) {
if(root==null){
return;
}
if(root.left==null && root.right==null){
minDepth=Math.min(minDepth,depth);
return;
}
dfs(root.left,depth+1);
dfs(root.right,depth+1);
}
}
bfs
class Solution {
public int minDepth(TreeNode root) {
if(root==null)
return 0;
Deque<TreeNode>queue=new LinkedList<>();
queue.addLast(root);
int minDepth=1;
while (!queue.isEmpty()){
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curNode = queue.remove();
if(curNode.left==null && curNode.right==null) //第一个叶子节点即返回
return minDepth;
if(curNode.left!=null)
queue.addLast(curNode.left);
if(curNode.right!=null)
queue.addLast(curNode.right);
}
minDepth++;
}
return minDepth;
}
}
二叉树最大宽度
添加链接描述
本题难点在于两节点之间的null节点也算数。
树的层序遍历是肯定的，在基础求宽度的题目基础上，记录节点在当前层的横向索引位置pos。然后最右和最左pos的差值即为宽度。
class Solution {
class Node{ //这不比map省内存多了
int pos;
TreeNode node;
public Node(TreeNode node,int pos){
this.node=node;
this.pos=pos;
}
}
public int widthOfBinaryTree(TreeNode root) {
if(root==null){
return 0;
}
Deque<Node>queue=new ArrayDeque<>();
queue.offer(new Node(root,1));
int ans=-1;
while (!queue.isEmpty()){
int size=queue.size();
int left=0;
int right=0;
for (int i = 0; i < size; i++) {
Node poll = queue.poll();
int pos=poll.pos;
TreeNode node=poll.node;
if(node.left!=null){
queue.offer(new Node(node.left,2*pos-1));
}
if(node.right!=null){
queue.offer(new Node(node.right,2*pos));
}
if(i==0){
left=pos;
}
if(i==size-1){
right=pos;
}
}
//计算最大宽度
ans=Math.max(ans,right-left+1);
}
return ans;
}
}