⼆叉树的中序遍历算法（Java三种实现⽅法）
⽂章⽬录
题⽬
给定⼀个⼆叉树的根节点 root ，返回它的 中序 遍历
⼀、⼆叉树的节点定义
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;
}
}
⼆、三种遍历⽅法
1.递归
算法思想
我们都知道中序遍历就是先遍历节点的左⼦树节点，然后访问根节点，最后再遍历右⼦树。⽽在访问左⼦树或者右⼦树的时候我们按照同样的⽅式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质。
代码如下：
class Solution {
public List<Integer>inorderTraversal(TreeNode root){
List<Integer> list =new ArrayList<Integer>();
inoder(root, list);
return list;
}
// 递归遍历
public void inoder(TreeNode root,List list){
if(root ==null){//如果节点为null  这直接退出递归
return;
}
inoder(root.left, list);// 访问左⼦树
list.add(root.val);// 将节点的值存⼊到list中
inoder(root.right,list);//访问右⼦树
}
}
先序中序后序遍历二叉树
复杂度分析：
时间复杂度：O(n)。其中 n 为⼆叉树节点的个数。⼆叉树的遍历中每个节点会被访问⼀次且只会被访问⼀次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，⽽栈深度在⼆叉树为⼀条链的情况下会达到 O(n) 的级别。
2.迭代
算法思想
递归函数我们也可以⽤迭代的⽅式实现，两种⽅式是等价的，区别在于递归的时候隐式地维护了⼀个栈，⽽我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同。
代码如下：
class Solution {
// 迭代遍历通过压栈和出栈来模拟递归过程本质和上⾯的递归是⼀样的
public List<Integer>inorderTraversal(TreeNode root){
List<Integer> res =new ArrayList<Integer>();
Deque<TreeNode> stk =new LinkedList<TreeNode>();//初始化栈
while(root !=null||!stk.isEmpty()){// 如果节点为空或栈为空则遍历结束
while(root !=null){//如果根节点不为空
stk.push(root);// 将根节点压栈
root = root.left;//访问左⼦树
}
root = stk.pop();// 存在节点为空此时栈中从栈顶的元素⼀定为⼦树的最左边⼀个⼦节点
res.add(root.val);// 将⼦节点存⼊列表中
root = root.right;//访问右节点
}
return res;
}
}
复杂度分析：
时间复杂度：O(n)。其中 n 为⼆叉树节点的个数。⼆叉树的遍历中每个节点会被访问⼀次且只会被访问⼀次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，⽽栈深度在⼆叉树为⼀条链的情况下会达到 O(n) 的级别。
3.Morris 中序遍历
算法思想
Morris 遍历算法是另⼀种遍历⼆叉树的⽅法，它能将⾮递归的中序遍历空间复杂度降为 O(1)。
Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 x）：
1. 如果 x ⽆左孩⼦，先将 x 的值加⼊答案数组，再访问 x 的右孩⼦，即 x=x.right。
2. 如果 x 有左孩⼦，则到 xx左⼦树上最右的节点（即左⼦树中序遍历的最后⼀个节点，x在中序遍历中的前驱节点），我们记为
predecessor。根据 predecessor 的右孩⼦是否为空，进⾏如下操作。
1. 如果 predecessor 的右孩⼦为空，则将其右孩⼦指向 x，然后访问 x的左孩⼦，即 x=x.left。
2. 如果 predecessor 的右孩⼦不为空，则此时其右孩⼦指向 x，说明我们已经遍历完 x 的左⼦树，我们
将 predecessor 的右孩
⼦置空，将 x 的值加⼊答案数组，然后访问 x 的右孩⼦，即 x = x.right。
重复上述操作，直⾄访问完整棵树
代码如下：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。