写在前言
(感谢代码随想录博主 博主是c++代码，此刷题总结是java代码，下文是我学习博主刷题记录的笔记)
递归三部曲：
-
找终止条件：什么时候递归到头了？
- 思考返回值，每一级递归应该向上返回什么信息？
-
单步操作应该怎么写？因为递归就是大量的调用自身的重复操作，因此从宏观上考虑，只用想想单步怎么写就行了，左树和右树应该看成一个整体，即此时树一共三个节点：root，root.left，root.right。
1.二叉树的遍历
1.递归版本
1.前序遍历；先访问根结点，然后再访问左子树，最后访问右子树
2.中序遍历；先访问左子树，中间访问根节点，最后访问右子树。此种方式遍历结果，会使结点有序
3.后序遍历；先访问左子树，再访问右子树，最后访问根节点
//使用3中方式遍历，获取整个树中的所有值
public void values(TreeNode root) {
preErgodic(root);
midErgodic(root);
afterErgodic(root);
}
/**
* 前序遍历实现步骤：
* 1.打印当前节点;
* 2.找到当前结点的左子树，如果不为空，递归遍历左子树
* 3.找到当前结点的右子树，如果不为空，递归遍历右子树
*/
private void preErgodic(TreeNode node) {
if (node == null) return;//如果当前节点为空，就直接返回
System.out.println(node.val);//保存当前节点的值
if (node.left != null) preErgodic(node.left);//遍历左边
if (node.right != null) preErgodic(node.right);//遍历右边
}
/**
* 中序遍历实现步骤：
* 1.找到当前结点的左子树，如果不为空，递归遍历左子树
* 2.打印当前节点;
* 3.找到当前结点的右子树，如果不为空，递归遍历右子树
*/
private void midErgodic(TreeNode node) {
if(node==null) return;
if(node.left!=null) midErgodic(node.left);
System.out.println(node.val);//保存当前节点的值
if(node.right!=null) midErgodic(node.right);
}
/**
* 后序遍历实现步骤：
* 1.找到当前结点的左子树，如果不为空，递归遍历左子树
* 2.找到当前结点的右子树，如果不为空，递归遍历右子树
* 3.打印当前节点;
*/
private void afterErgodic(TreeNode node) {
if(node == null) return;
if(node.left!=null) afterErgodic(node.left);
if(node.right!=null) afterErgodic(node.right);
System.out.println(node.val);
}
2.非递归版本
思想：使用栈，因为递归版本就是系统帮你压栈，则可以想到我们使用非递归版本可以自己手动压栈。
前序遍历：使用一个栈，先把根节点压入进去，然后开始弹栈，然后压入当前节点的右节点，然后再压左节点，因为先进后出嘛，右节点先进去，则后打印 因为是栈 右节点先压入 说明后出来
public void pre(TreeNode root){
if (root == null) return;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode curNode = stack.pop();
System.out.print(curNode.val+" ");//处理节点
if(curNode.right!=null) stack.push(curNode.right);
if(curNode.left!=null) stack.push(curNode.left);
}
}
中序遍历：也是用一个栈，先把树的左节点全部压入进去，压完左节点就开始弹出一个当前节点，然后处理打印，并让当前节点指向它的右节点，继续循环，如果当前节点为null，就不能压栈，继续出栈
public void mid(TreeNode root){
if (root == null) return;
Stack<TreeNode> stack=new Stack<>();
while (!stack.isEmpty() || root!=null){
//如果当前节点不为Null，压栈
if(root !=null){
stack.push(root);
root=root.left;//让当前节点指向它的左子树
} else {
root = stack.pop();
System.out.print(root.val+" ");//处理节点
root=root.right;//让当前节点指向它的右子树
}
}
}
后序遍历：使用2个栈。stack先压入根节点，然后开始弹出，弹出后将当前节点放到stackNode栈中。如果当前节点有左节点，就压入左节点，如果有右节点，则压入右节点。最后打印stackNode栈就是后序遍历的顺序
public void after(TreeNode root){
if (root == null) return;
Stack<TreeNode> stack=new Stack<>();
Stack<TreeNode> stackNode=new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode curNode = stack.pop();
stackNode.push(curNode);
if(curNode.left!=null) stack.push(curNode.left);
if(curNode.right!=null) stack.push(curNode.right);
}
while (!stackNode.isEmpty())
System.out.print(stackNode.pop().val+" ");
}
3.层次遍历
实现步骤：
1.创建队列，存储每一层的结点；
2.使用循环从队列中弹出一个结点：
2.1获取当前结点的key；
2.2如果当前结点的左子结点不为空，则把左子结点放入到队列中
2.3如果当前结点的右子结点不为空，则把右子结点放入到队列中
public Queue<Integer> layerErgodic(){
Queue<Integer> values=new ArrayDeque<>();
ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
queue.add(root);//让根节点进入队列
while (!queue.isEmpty()){
//进入了循环，说明该队列中还有结点，则将该队首出队，保存到values中
TreeNode node = queue.remove();
values.add(node.val);
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
}
return values;
}
层次遍历进阶版：按层次输入元素:
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) return new ArrayList<>();
ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
queue.add(root);
List<List<Integer>> lists=new ArrayList<>();
while (!queue.isEmpty()){
List<Integer> layer=new ArrayList<>();
//进入了循环，说明该队列中还有结点，则将该队首出队，保存到每层的layer中
int count=queue.size();//用于保存每一层的元素节点个数
while (count>0){
TreeNode node = queue.poll();
layer.add(node.val);
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
count--;
}
lists.add(layer);
}
return lists;
}
找到树最后一行的第一个数
public int findBottomLeftValue(
