LeetCode算法（二叉树）
今天的练习的是一个新的数据结构：二叉树
这里我不太想去说一些比较规则正式的介绍了，简单说一下我觉得比较有用和算法题目相关的，因为东西挺多的，大家如果想更详细的了解二叉树，搜索一下其他大佬们的介绍！
二叉树的分类：
主要说一下我对满二叉树和完全二叉树的区别理解：
满二叉树是指所有的叶子节点位置都有数据
完全二叉树是指，在满二叉树的基础上，允许右分支为空，只需要满足左分支有节点即可
二叉树节点：
在开始二叉树算法之前，我们需要自己构建出一个二叉树，也就是其节点
节点需要三个属性，分别是：该节点的数据，左分支节点，右分支节点
代码如下：
public class TreeNode {
/*
二叉数的节点
节点包括三个部分:
1.该节点存储的数值
2.该节点的左分支节点
3.该节点的右分支节点
*/
public Integer val;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
public TreeNode(Integer val) {
this.val = val;
}
public TreeNode(Integer val, TreeNode leftNode, TreeNode rightNode) {
this.val = val;
this.left = leftNode;
this.right = rightNode;
}
}
如果大家跟着有困难，还是先去了解一下二叉树。
二叉树遍历（递归）：
链接：前序遍历
后序遍历
中序遍历
首先我们需要知道如何去遍历一个二叉树，有两种方法，一种是递归法，另一种是迭代法
对于递归算法来说，我们需要三点：
1.停止的条件
2.每次递归时必要的参数，和返回值
3.每次进行递归中的处理逻辑
对于停止条件，也就是什么时候我们停止遍历二叉树，当然是当前遍历的节点为空时，停止本次的递归
其次是参数与返回值，参数就是下一个节点，当我们处理完一个节点后，是不需要再处理其他什么的，所以忽略返回值
最后就是执行递归的逻辑：
第一步，就是对停止条件进行判断，如果达到条件便停止
第二步，将本次遍历的节点数据添加到结果集中
第三步，开始递归，将本节点的左节点或者右节点当作参数传入
代码如下：
import java.util.ArrayList;
import java.util.List;
public class RecursiveTraversalOfBinaryTree {
/*
递归遍历二叉树
*/
/*
1.传入一个TreeNode,也就是根节点,新建一个数组,将其传入递归方法
2.新建一个递归方法,分析每个节点是否存在也就是判null,如果不为null,则证明是一个节点
将其存储的数值添加到数组中,然后取出其左分支节点和右分支节点,然后进行递归
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
produceBefore(root,result);
return result;
}
//前序遍历
private void produceBefore(TreeNode root,List<Integer> result){
//判断node节点是否存在
if (root == null){
return;
}
result.add(root.val);
produceBefore(root.left,result);
produceBefore(root.right,result);
}
//中序遍历
private void produce(TreeNode root,List<Integer> result){
//判断node节点是否存在
if (root == null){
return;
}
produce(root.left,result);
result.add(root.val);
produce(root.right,result);
}
}
然后说一下，前序遍历，中序遍历，后序遍历的区别，就是根节点所在的位置
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中
那么我们只需要改变递归逻辑就好了，root.left就是左，root.val就根节点，root.right就右，按照上述的顺序，对应写好，就完成了每个遍历顺序
二叉树遍历（迭代）：
如果使用迭代法的话，需要借用另一个数据结构，栈
栈的主要目的就是存储已经遍历过节点，而递归实际上就是将当前遍历的节点作为参数传入，所以栈也可以实现遍历二叉树
那么对应的思路就是，当我们开始遍历时，将当前节点压入到栈中，在下一次迭代时，进行弹栈处理，如果是前序遍历，则先将右节点压入再压左节点，因为栈的特点是先进后出，只有将先弹出的节点后放入，才能优先出来。而后序遍历只需要改变一下顺序，先压左节点再压右节点，它的顺序就是：中右左，最后将该结果进行反转，变成左右中就好了
中序遍历与前后序遍历不同，因为前后序遍历最先处理的都是中，也就是根节点，而中序遍历是需要先处理叶子节点，所以我们的目标应该是遍历到叶子节点再开始进行处理
所以使用的是指针的方式，通过指针定位到我们想处理的节点，然后再利用入栈弹栈来进行对应的处理。首先将指针定位到根节点，然后开始遍历，如果指针不为空，那么就一直寻找节点的左节点，并将遍历到的节点全部压入到栈中，这样，当遍历到底部时，会触发弹栈，将最后一个左节点取出，添加到结果集，此时指针还是为空，因为该节点没有右分支呀，那么还会触发弹栈，会将该节点的根节点取出，进行结果集的添加，并处理该节点的右分支。
代码如下：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
public class IterativelyTraversingBinaryTree {
/*
迭代遍历二叉树
*/
/*
利用栈来进行遍历(前序遍历)(中左右)
1.将根节点压入到栈中,然后对栈进行判断,因为栈如果不为空,则证明还有其他节点
2.从根节点开始遍历,也就是将其弹出栈,然后添加到结果数组
3.判断其右分支是否有节点,如果有则压入栈中,左侧同理,因为栈是先进后出,所以先压右再压左,保证左先出
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
result.add(pop.val);
if (pop.right != null) {
stack.push(pop.right);
}
if (pop.left != null) {
stack.push(pop.left);
}
}
return result;
}
/*
中序遍历(指针)
1.传入根节点,对根节点进行判断,如果为空则直接返回空数组
2.栈如果不为空则证明还有节点,新建一个指针,指向根节点
进入循环,如果栈为空,或者指针为空,则证明没有节点,否则一直找下去
3.一直遍历二叉树到左分支的叶子节点,并让指针指向该节点,下次进入循环,那么指针一定为空,进行弹栈
弹栈的节点为左分支的叶子节点,并将其添加到数组中,并将指针指向该节点的右分支节点
此时指针还是空,所以进行弹栈,这时节点为其父节点,添加到数组,然后指针指向其右分支节点,也就是右分支的叶子节点
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
/*
后序遍历(左右中) 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode pop = stack.pop();
result.add(pop.val);
if (pop.left != null){
stack.push(pop.left);
}
if (pop.right != null){
stack.push(pop.right);
}
}
Collections.reverse(result);
return result;
}
}
二叉树的层序遍历：
链接：层序遍历
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑
思路：利用队列存储每个节点，然后处理每个节点的左右分支，并保存在队列中
提前记录队列的size，当size为0也就是处理完本次的所有节点后，将数据放入结果集，然后开始下一次也就是下一层的处理
利用队列的先进先出
1.分为两个循环,一个是层级循环,一个是节点查找
2.在大循环,也就是层级循环时,创建数组,为该层的数据
判断队列的长度,如果大于0,则证明该层有节点,开始节点查找,进入小循环
将节点取出,队列长度减一,然后添加到该层的数组中,然后判断其左分支节点和右分支节点是否存在,如果存在则添加到队列里
并将这层的数组添加到结果里
代码如下：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class TraverseBinaryTreeHierarchy {
/*
二叉树的层级遍历
*/
/*
利用队列的先进先出
1.分为两个循环,一个是层级循环,一个是节点查找
2.在大循环,也就是层级循环时,创建数组,为该层的数据
判断队列的长度,如果大于0,则证明该层有节点,开始节点查找,进入小循环
将节点取出,队列长度减一,然后添加到该层的数组中,然后判断其左分支节点和右分支节点是否存在,如果存在则添加到队列里
并将这层的数组添加到结果里
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
//每层
while (!queue.isEmpty()) {
List<Integer> list = new ArrayList<>();
int size = queue.size();
//每层的每个节点
while (size > 0){
TreeNode poll = queue.poll();
list.add(poll.val);
if (poll.left!=null){
queue.offer(poll.left);
}
if (poll.right!=null){
queue.offer(poll.right);
}
//已经处理完了该层的一个节点
size--;
}
//层的所有节点已经结束了
result.add(list);
}
return result;
}
}
二叉树的右视图：
链接：右视图
如果掌握了层序遍历，利用队列特性来处理节点，那么右视图也很简单了
刚开始我以为直接拿取所有右分支节点不好了，后面一想，没有右分支，那么左分支不就成了右视图的一部分，所以还是要把左分支考虑进去
那么在层级遍历的基础上，当我们把每层的节点压入到队列后，只需要拿取队列中的最后一个节点，就是右视图中的节点了，也就是size = 1时
代码如下：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class RightVewOfBinaryTree {
/*
二叉树的右视图
*/
/*
利用队列,首先将根节点放入到队列里,然后利用层遍历,取出节点,
判断是否有左右节点,然后添加到队列里,
如果是该层的最后一个节点,那么将其添加到队列里
*/
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode poll = queue.poll();
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
if (size == 1) {
result.add(poll.val);
}
size--;
}
}
return result;
}
}
二叉树的最大深度：
链接：最大深度
最大深度还是和层级遍历相联系，所谓最大深度变成层级遍历的问题就是，当队列的size为0时，达到最大深度
所以我们还是利用队列，和层级遍历，每当我们进行层遍历的时候，对最大深度加1
当队列为空时，返回最大深度即可
代码如下：
import java.util.LinkedList;
import java.util.Queue;
public class TheMaximumDepthOfBinaryTree {
/*
二叉树的最大深度
*/
/*
首先还是层遍历,当队列数量为空的时候,层的深度加1
*/
public int maxDepth(TreeNode root) {
int maxDepth = 0;
if (root == null) {
return maxDepth;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
maxDepth++;
while (size > 0){
TreeNode poll = queue.poll();
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
size--;
}
}
return maxDepth;
}
}
二叉树的直径：
这道题真的是简单题吗哈哈哈我觉得有点难度，中等偏上，这个递归开始让我没搞懂，那我来说说我的理解
首先是递归的三要素：终止条件，传递的参数和返回的结果，递归的逻辑
直径是左分支最大值 + 右分支最大值
那么终止条件一定是，当遍历到最底层的叶子节点是停止，证明遍历完毕
传递的参数应该是每次递归时所需要的节点，因为直径只考虑深度不需要考虑具体的节点值
对于返回值来说，当我们递归到树的最底层的叶子节点时，实际上才是计算的开始
也就是说，是从底部往上算的，那返回的应该是自增1，因为递归到底部的叶子节点，是终止条件，返回的是0，那么它的上一个节点再次返回，应该是1，再返回应该2......这是第一点
第二点就是需要考虑节点的左右分支，因为直径是根节点的左分支最长加右分支最长，而每个节点又有左分支和右分支，所以，只需要每个节点返回的左右分支中的最大值就好了
到了递归的逻辑，就是获取每个节点的左节点深度，和右节点深度，然后相加，然后与全局最大直径比较更新。
代码如下：
import java.util.LinkedList;
import java.util.Queue;
public class TheDiameterOfBinaryTree {
/*
二叉树的直径
*/
/*
计算每个节点的深度
直径 等于 左树加右树的深度
首先对节点进行判空处理,为空则返回0
然后计算节点左树和右树节点深度
更新直径的大小,判断当前直径大小 和 节点左树加右树的深度之和 的最大值
最后返回该节点的深度
*/
private int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null){
return 0;
}
calculateDepth(root);
return diameter; // 返回全局最大直径
}
private int calculateDepth(TreeNode node) {
if (node == null){
return 0;
}
int left = calculateDepth(node.left);
int right = calculateDepth(node.right);
diameter = Math.max(left + right,diameter);
return Math.max(left,right);
}
}
从前序与中序遍历序列构造二叉树：
链接：从前序与中序遍历序列构造二叉树
这道题我也是看了别的大佬们写的，才看懂的，大佬写的很详细，我在上面改进了一点，更多是看起来更详细吧，还有注释
参考：【算法】从前序与中序遍历序列构建二叉树_从前序与中序遍历序列构造二叉树-CSDN博客
代码如下：
import java.util.HashMap;
import java.util.Map;
public class ConstructBinaryTreeFromPreorderAndInorder {
/*
从前序与中序遍历序列构造二叉树
*/
/*
1.根据中序遍历来进行分割,首先将中序遍历的数组放入hashmap中,key为值,value为对应索引
2.利用递归构建二叉树,将前序遍历的数组,开始值,中序遍历数组的最大索引传入,因为需要分割中序遍历的数组
3.确定递归返回值: 为根节点 因为前序和中序遍历的都是同一棵树,所以对应的子树的节点数量也一样
首先根据前序遍历数组获取根节点,然后移动前序数组的指针
根据根节点对中序遍历数组进行分割,分成
*/
private Map<Integer, Integer> inorderIndexMap;
private int preorderIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 创建一个哈希表来快速查找中序遍历中元素的索引
inorderIndexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderIndexMap.put(inorder[i], i);
}
return buildTreeHelper(preorder, 0, inorder.length - 1);
}
private TreeNode buildTreeHelper(int[] preorder, int inorderStart, int inorderEnd) {
if (inorderStart > inorderEnd) {
return null;
}
// 根节点是前序遍历中的第一个元素
int rootValue = preorder[preorderIndex];
preorderIndex++;
// 在中序遍历中找到根节点的索引
int rootIndex = inorderIndexMap.get(rootValue);
// 分割中序遍历数组
int leftSubtreeSize = rootIndex - 1;
int rightSubtreeSize = rootIndex + 1;
// 递归构建左子树和右子树
TreeNode root = new TreeNode(rootValue);
root.left = buildTreeHelper(preorder, inorderStart, leftSubtreeSize);
root.right = buildTreeHelper(preorder, rightSubtreeSize, inorderEnd);
return root;
}
}
今天的练习就到这里了！二叉树的题很多，我觉得最重要的就层序遍历那块了，掌握层序就会了好多类似的题，感谢大家！