理论基础
-
二叉树的种类
- 满二叉树
- 完全二叉树
- 二叉搜索树
- 平衡二叉搜索树
-
存储方式：数组、链式
-
二叉树的遍历方式
- 深度优先遍历
- 前序（递归法、迭代法）
- 中序（递归法、迭代法）
- 后序（递归法、迭代法）
- 广度优先遍历
- 层序（迭代法）
- 深度优先遍历
-
二叉树的定义
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val=val;}
TreeNode(int val,TreeNode left,TreeNode right)
{
this.val=val;
this.left=left;
this.right=right;
}
}
递归遍历
递归三要素
- 确定递归函数的参数和返回值
- 确定终止条件
- 确定单层递归的逻辑
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// 前序遍历：中左右
List<Integer> result=new ArrayList<Integer>();
pre(root,result);
return result;
}
public void pre(TreeNode root,List<Integer> result)
{
if(root==null)
return;
result.add(root.val);
pre(root.left,result);
pre(root.right,result);
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// 中序遍历：左中右
List<Integer> result=new ArrayList<Integer>();
inorder(root,result);
return result;
}
public void inorder(TreeNode root,List<Integer> result)
{
if(root==null)
return;
inorder(root.left,result);
result.add(root.val);
inorder(root.right,result);
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// 后序遍历：左右中
List<Integer> result=new ArrayList<Integer>();
postorder(root,result);
return result;
}
public void postorder(TreeNode root,List<Integer> result)
{
if(root==null)//递归终止条件
return;
postorder(root.left,result);
postorder(root.right,result);
result.add(root.val);
}
}
层序遍历
- 队列实现层序遍历：先进先出
二叉树的层序遍历
102.二叉树的层序遍历(opens new window)
- 迭代法
class Solution {
public List<List<Integer>> reList=new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
check(root);
return reList;
}
public void check(TreeNode node){
//判空
if(node==null)
return;
Queue<TreeNode> q=new LinkedList<TreeNode>();
//根节点 入队
q.offer(node);
while(!q.isEmpty())
{
List<Integer> itemlist=new ArrayList<Integer>();//存放每层节点
int lens=q.size();
while(lens>0)
{
TreeNode tmp=q.poll();//出队
itemlist.add(tmp.val);
if(tmp.left!=null)
{
q.offer(tmp.left);
}
if(tmp.right!=null)
{
q.offer(tmp.right);
}
lens--;
}
reList.add(itemlist);
}
}
}
- 递归法
class Solution {
public List<List<Integer>> reList=new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
check(root,0);
return reList;
}
public void check(TreeNode node,int deep) {
if(node==null) return;//终止条件
deep++;
if(reList.size()<deep)
{
List<Integer> itemlist=new ArrayList<>();
reList.add( itemlist);
}
reList.get(deep-1).add(node.val);//根据索引寻找对应层数
check(node.left,deep);
check(node.right,deep);
}
}
二叉树的层次遍历II
107.二叉树的层次遍历II(opens new window)
class Solution {
public List<List<Integer>> reList=new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrderBottom(TreeNode root) {
check(root);
//翻转
List<List<Integer>> result=new ArrayList<List<Integer>>();
for(int i=reList.size()-1;i>=0;i--)
{
result.add(reList.get(i));
}
return result;
}
public void check(TreeNode node){
//判空
if(node==null)
return;
Queue<TreeNode> q=new LinkedList<TreeNode>();
//根节点 入队
q.offer(node);
while(!q.isEmpty())
{
List<Integer> itemlist=new ArrayList<Integer>();//存放每层节点
int lens=q.size();
while(lens>0)
{
TreeNode tmp=q.poll();//出队
itemlist.add(tmp.val);
if(tmp.left!=null)
{
q.offer(tmp.left);
}
if(tmp.right!=null)
{
q.offer(tmp.right);
}
lens--;
}
reList.add(itemlist);
}
}
}
二叉树的右视图
class Solution {
public List<List<Integer>> reList=new ArrayList<List<Integer>>();
public List<Integer> rightSideView(TreeNode root) {
check(root);
List<Integer> result=new ArrayList<Integer>();
for(int i=0;i<reList.size();i++)
{
int lens=reList.get(i).size();//每层的个数
result.add(reList.get(i).get(lens-1));//每层的最后一个
}
return result;
}
public void check(TreeNode node){
//判空
if(node==null)
return;
Queue<TreeNode> q=new LinkedList<TreeNode>();
//根节点 入队
q.offer(node);
while(!q.isEmpty())
{
List<Integer> itemlist=new ArrayList<Integer>();//存放每层节点
int lens=q.size();
while(lens>0)
{
TreeNode tmp=q.poll();//出队
itemlist.add(tmp.val);
if(tmp.left!=null)
{
q.offer(tmp.left);
}
if(tmp.right!=null)
{
q.offer(tmp.right);
}
lens--;
}
reList.add(itemlist);
}
}
}
二叉树的层平均值
637.二叉树的层平均值(opens new window)
class Solution {
public List<List<Integer>> reList=new ArrayList<List<Integer>>();
public List<Double> averageOfLevels(TreeNode root) {
check(root);
List<Double> result=new ArrayList<>();
for(int i=0;i<reList.size();i++)
{
int lens=reList.get(i).size();//每层的个数
double itemSum=0;
for(int j=0;j<lens;j++)
{
itemSum+=reList.get(i).get(j);
}
result.add(itemSum/lens);
}
return result;
}
public void check(TreeNode node){
//判空
if(node==null)
return;
Queue<TreeNode> q=new LinkedList<TreeNode>();
//根节点 入队
q.offer(node);
while(!q.isEmpty())
{
List<Integer> itemlist=new ArrayList<Integer>();//存放每层节点
int lens=q.size();
while(lens>0)
{
TreeNode tmp=q.poll();//出队
itemlist.add(tmp.val);
if(tmp.left!=null)
{
q.offer(tmp.left);
}
if(tmp.right!=null)
{
q.offer(tmp.right);
}
lens--;
}
reList.add(itemlist);
}
}
}
N叉树的层序遍历
429.N叉树的层序遍历(opens new window)
class Solution {
public List<List<Integer>> reList=new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(Node root) {
check(root);
return reList;
}
public void check(Node node){
//判空
if(node==null)
return;
Queue<Node> q=new LinkedList<Node>();
//根节点 入队
q.offer(node);
while(!q.isEmpty())
{
List<Integer> itemlist=new ArrayList<Integer>();//存放每层节点
int lens=q.size();
while(lens>0)
{
Node tmp=q.poll();//出队
itemlist.add(tmp.val);
List<Node> children=tmp.children;
/* if(children==null||children.size()==0)
{
continue;
}*/
for(Node child:children)
{
if(child!=null)
{
q.offer(child);
}
}
lens--;
}
reList.add(itemlist);
}
}
}
在每个树行中找最大值
515.在每个树行中找最大值(opens new window)
class Solution {
public List<List<Integer>> reList=new ArrayList<List<Integer>>();
public List<Integer> largestValues(TreeNode root) {
check(root);
List<Integer> result=new ArrayList<>();
for(int i=0;i<reList.size();i++)
{
int lens=reList.get(i).size();
int max=reList.get(i).get(0);
for(int j=1;j<lens;j++)
{
if(reList.get(i).get(j)>max)
{
max=reList.get(i).get(j);
}
}
result.add(max);
}
return result;
}
public void check(TreeNode node){
//判空
if(node==null)
return;
Queue<TreeNode> q=new LinkedList<TreeNode>();
//根节点 入队
q.offer(node);
while(!q.isEmpty())
{
List<Integer> itemlist=new ArrayList<Integer>();//存放每层节点
int lens=q.size();
while(lens>0)
{
TreeNode tmp=q.poll();//出队
itemlist.add(tmp.val);
if(tmp.left!=null)
{
q.offer(tmp.left);
}
if(tmp.right!=null)
{
q.offer(tmp.right);
}
lens--;
}
reList.add(itemlist);
}
}
}
填充每个节点的下一个右侧节点指针
116.填充每个节点的下一个右侧节点指针(opens new window)
节点的下一个右侧节点指针II
117节点的下一个右侧节点指针II(opens new window)
二叉树的最大深度
104.二叉树的最大深度(opens new window)
class Solution {
public List<List<Integer>> reList=new ArrayList<List<Integer>>();
public int maxDepth(TreeNode root) {
check(root);
return reList.size();
}
public void check(TreeNode node){
//判空
if(node==null)
return;
Queue<TreeNode> q=new LinkedList<TreeNode>();
//根节点 入队
q.offer(node);
while(!q.isEmpty())
{
List<Integer> itemlist=new ArrayList<Integer>();//存放每层节点
int lens=q.size();
while(lens>0)
{
TreeNode tmp=q.poll();//出队
itemlist.add(tmp.val);
if(tmp.left!=null)
{
q.offer(tmp.left);
}
if(tmp.right!=null)
{
q.offer(tmp.right);
}
lens--;
}
reList.add(itemlist);
}
}
}
二叉树的最小深度