代码随想录算法训练营Day13|二叉树

二叉树理论基础

二叉树类型

满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

如图所示：

这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

完全二叉树

什么是完全二叉树？

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

如图：

二叉树的存储方式

链式存储

顺序存储

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的遍历方式

二叉树主要有两种遍历方式：

• 深度优先遍历

  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）

一般采用递归来实现，而栈是实现递归的一种常用结构

• 广度优先遍历

  • 层次遍历（迭代法）

一般采用队列来实现

二叉树的定义

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;
}
}

三种构造方法，分别是啥都不传，只传节点值，传节点值和左右指针指向

递归遍历

题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html

递归算法的三个要素，每次写递归，都按照这三要素来写，可以保证写出正确的递归算法！

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}

public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}

void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val); // 注意这一句
inorder(root.right, list);
}
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}

void postorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postorder(root.left, list);
postorder(root.right, list);
list.add(root.val); // 注意这一句
}
}

前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[1,2,3]

解释：

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

解释：

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

/**
* Definition for a binary tree node.
* 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> list=new ArrayList<>();
preorder(root,list);
return list;
}

public void preorder(TreeNode root,List<Integer> list){
if(root==null){
return;
}
list.add(root.val);
preorder(root.left,list);
preorder(root.right,list);
}
}

前序遍历决定 list.add(root.val)在最前

中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

/**
* Definition for a binary tree node.
* 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> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
inorder(root,list);
return list;
}

public void inorder(TreeNode root,List<Integer> list){
if(root==null){
return;
}
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
}

后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]

输出：[3,2,1]

解释：

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[4,6,7,5,2,9,8,3,1]

解释：

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

/**
* Definition for a binary tree node.
* 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> postorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
postorder(root,list);
return list;
}

public void postorder(TreeNode root,List<Integer> list){
if(root==null){
return;
}
postorder(root.left,list);
postorder(root.right,list);
list.add(root.val);
}
}

迭代遍历

统一迭代

层序遍历

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

/**
* Definition for a binary tree node.
* 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 {
List<List<Integer>> list=new ArrayList<List<Integer>>();

public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null)return list;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
List<Integer> templist=new ArrayList<Integer>();
while(size>0){
TreeNode node=queue.poll();
templist.add(node.val);
size–;
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
}
list.add(templist);
}
return list;
}
}

用队列进行解决，遍历一个节点，就把这个节点弹出，并把这个节点的左右节点存入队列，直到队列为空（最后弹出的节点左右节点都为空）

102.二叉树的层序遍历

• 102.二叉树的层序遍历(opens new window)

就是这道母题不再赘述

107.二叉树的层序遍历II

• 107.二叉树的层序遍历II(opens new window)

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

/**
* Definition for a binary tree node.
* 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 {
List<List<Integer>> list=new LinkedList<List<Integer>>();
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if(root==null)return list;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
List<Integer> templist=new ArrayList<Integer>();
while(size>0){
TreeNode node=queue.poll();
templist.add(node.val);
size–;
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
}
list.addFirst(templist);
}
return list;
}
}

   list.addFirst(templist);直接将每层元素的集合添加到list集合的最前面即可（避免倒序操作）

199.二叉树的右视图

• 199.二叉树的右视图(opens new window)

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

输入：root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

示例 2：

输入：root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

解释：

示例 3：

输入：root = [1,null,3]

输出：[1,3]

示例 4：

输入：root = []

输出：[]

/**
* Definition for a binary tree node.
* 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 {
List<Integer> list=new ArrayList<Integer>();
public List<Integer> rightSideView(TreeNode root) {
if(root==null)return list;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
while(size>0){
TreeNode node=queue.poll();
if(size==1){
list.add(node.val);
}
size–;
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
}
}
return list;
}
}

其实就是把每层元素集合中的最后一个元素添加到list集合中就行

637.二叉树的层平均值

• 637.二叉树的层平均值(opens new window)

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

/**
* Definition for a binary tree node.
* 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 {
List<Double> list =new ArrayList<Double>();
public List<Double> averageOfLevels(TreeNode root) {
if(root==null)return list;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
int size1=queue.size();
double num=0.0;
while(size>0){
TreeNode node=queue.poll();
num+=node.val;
size–;
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
}
list.add(num/size1);
}
return list;
}
}

计算每层的平均值存入list即可

429.N叉树的层序遍历

• 429.N叉树的层序遍历(opens new window)

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
List<List<Integer>> list=new ArrayList<List<Integer>>();

public List<List<Integer>> levelOrder(Node root) {
if(root==null)return list;
Queue<Node> queue=new LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
List<Integer> templist=new ArrayList<Integer>();
while(size>0){
Node node=queue.poll();
templist.add(node.val);
size–;
for(Node node1:node.children){
if(node1!=null)queue.offer(node1);
}
}
list.add(templist);
}
return list;
}
}

其实本质上和二叉树一样，二叉树是两个孩子节点，N叉树是n个孩子节点

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

• 515.在每个树行中找最大值(opens new window)

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：

输入: root = [1,2,3]
输出: [1,3]

/**
* Definition for a binary tree node.
* 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 {
List<Integer> list=new ArrayList<Integer>();
public List<Integer> largestValues(TreeNode root) {
if(root==null)return list;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
int max=Integer.MIN_VALUE;
while(size>0){
TreeNode node=queue.poll();
if(node.val>max)max=node.val;
size–;
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
}
list.add(max);
}
return list;
}
}

每层元素找出最大值，然后把最大值存入list就行

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

• 116.填充每个节点的下一个右侧节点指针(opens new window)

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;

public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/

class Solution {
public Node connect(Node root) {
if(root==null)return root;
Queue<Node> queue=new LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
while(size>0){
Node node=queue.poll();
if(size>1){
node.next=queue.peek();
}else{
node.next=null;
}
size–;
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
}
}
return root;
}
}

看似变了，其实还是没有变，只要把队列poll的每个节点的next指向队列的新队首（peek）就行

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

• 117.填充每个节点的下一个右侧节点指针II(opens new window)

给定一个二叉树：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2：

输入：root = []
输出：[]

/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;

public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/

class Solution {
public Node connect(Node root) {
if(root==null)return root;
Queue<Node> queue=new LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
while(size>0){
Node node=queue.poll();
if(size>1){
node.next=queue.peek();
}else{
node.next=null;
}
size–;
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
}
}
return root;
}
}

和上面那题一样，连代码都一样

104.二叉树的最大深度

• 104.二叉树的最大深度(opens new window)

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2
/**
* Definition for a binary tree node.
* 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 int maxDepth(TreeNode root) {
int num=0;
if(root==null)return num;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
while(size>0){
TreeNode node=queue.poll();
size–;
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
}
num++;
}
return num;
}
}

只需要返回循环的次数即可

111.二叉树的最小深度

• 111.二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

/**
* Definition for a binary tree node.
* 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 int minDepth(TreeNode root) {
int num=0;
if(root==null)return num;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
while(size>0){
TreeNode node=queue.poll();
size–;
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
num++;
if(node.left==null&&node.right==null)return num;
}
}
return num;
}
}

就是添加一个return，第一次左右子节点都是null的时候，return num