今天的练习的是一个新的数据结构：二叉树
这里我不太想去说一些比较规则正式的介绍了，简单说一下我觉得比较有用和算法题目相关的，因为东西挺多的，大家如果想更详细的了解二叉树，搜索一下其他大佬们的介绍！
二叉树的分类：
主要说一下我对满二叉树和完全二叉树的区别理解：
满二叉树是指所有的叶子节点位置都有数据
完全二叉树是指，在满二叉树的基础上，允许右分支为空，只需要满足左分支有节点即可
二叉树节点：
在开始二叉树算法之前，我们需要自己构建出一个二叉树，也就是其节点
节点需要三个属性，分别是：该节点的数据，左分支节点，右分支节点
代码如下：
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;}}
今天的练习就到这里了！二叉树的题很多，我觉得最重要的就层序遍历那块了，掌握层序就会了好多类似的题，感谢大家！