最近刷题刷到二叉树...算法面试的常客，数据结构基石...
见到许多厉害的解法，膜拜啊~
特此记录一下2022/3/24
力扣对应题目：144,145,94
一：递归法一看就会，一写就废！~简单解法
前序遍历：
class Solution {
public List preorderTraversal(TreeNode root) {
List result = new ArrayList();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
中序遍历：
class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val); // 注意这一句
inorder(root.right, list);
}
}
后序遍历：
class Solution {
public List postorderTraversal(TreeNode root) {
List res = new ArrayList<>();
postorder(root, res);
return res;
}
void postorder(TreeNode root, List list) {
if (root == null) {
return;
}
postorder(root.left, list);
postorder(root.right, list);
list.add(root.val); // 注意这一句
}
}
二：迭代法
递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。so 可以用栈！
前序遍历：
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
public List preorderTraversal(TreeNode root) {
List result = new ArrayList<>();
if (root == null){
return result;
}
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
中序遍历：
class Solution {
public List inorderTraversal(TreeNode root) {
//中序遍历：左中右 入栈顺序：左右
List res = new ArrayList<>();
if(root == null){
return res;
}
Stack stack = new Stack<>();
TreeNode cur = root;
while(cur != null || stack.isEmpty()){
if(cur != null){
stack.push(cur);//头结点入栈
cur = cur.left;//一直遍历放左节点，到最左的叶子结点，
然后到else取出最左的结点，然后放右结点。左边-中间-右边
}else{
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
}
}
}
后续遍历：
class Solution {
public List postorderTraversal(TreeNode root) {
//左右中 入栈顺序：中左右 出栈顺序：中右左 翻转：左右中
List res = new ArrayList<>();
if(root == null){
return res;
}
Stack stack1 = new Stack<>();
stack1.push(root);//头结点入栈
while(!stack1.isEmpty()){
TreeNode node = stack1.pop();
res.add(node.val);
if(node.left != null){
stack1.push(node.left);
}
if(node.right != null){
stack1.push(node.right);
}
}
Collections.reverse(res);
return res;
}
}
三：统一迭代法
迭代法实现的先中后序，其实风格也不是那么统一，除了先序和后序，有关联，中序完全就是另一个风格了，一会用栈遍历，一会又用指针来遍历。
其实针对三种遍历方式，使用迭代法是可以写出统一风格的代码！
重头戏来了，接下来介绍一下统一写法。
用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
前序遍历：
class Solution {
public List preorderTraversal(TreeNode root) {
//前序：中左右 入栈顺序：右左中
List res = new ArrayList<>();//linkedList也可以
Stack st = new Stack<>();
if(root != null) st.push(root);
while(!st.empty()){
TreeNode node = st.peek();
if(node != null){
st.pop();//把该节点弹出，避免重复操作
if(node.right != null) st.push(node.right);
if(node.left != null) st.push(node.left);
st.push(node);
st.push(null);//中间结点访问过，但还没有处理，加入空节点标记
}else{
st.pop();//弹出空节点
node = st.pop();//取出被标记的结点
res.add(node.val);//加入res中
}
}
return res;
}
}
中序遍历：
后续遍历：
class Solution {
public List postorderTraversal(TreeNode root) {
//后序：左右中 入栈顺序：中右左
List res = new linkedList<>();
Stack st = new Stack<>();
if(root != null ) st.push(root);
while(!st.empty()){
TreeNode node = st.peek();
if(node != null){
st.pop();//弹出该节点，避免重复
st.push(node);
st.push(null);//中方结点访问过，没处理，标记
if(node.right != null) st.push(node.right);
if(node.left != null) st.push(node.left);
}else{
st.pop();//把null结点弹出
node = st.pop();
res.add(node.val);
}
}
return res;
}
}
