中序遍历的两种实现——二叉树专题复习

递归实现：

/*** Definition for a binary tree node.* 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;*     }* }*/
class Solution {// 定义一个结果列表，用于存储遍历的结果List<Integer> res = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {// 调用递归的中序遍历方法inorder(root);// 返回中序遍历的结果列表return res;}// 递归的中序遍历方法public void inorder(TreeNode root){// 如果当前节点为空，则返回if(root == null) return;// 递归地对左子树进行中序遍历inorder(root.left);// 将当前节点的值添加到结果列表res.add(root.val);// 递归地对右子树进行中序遍历inorder(root.right);}
}

递归和迭代的中序遍历在逻辑上是等价的，它们都遵循“左-根-右”的遍历顺序。区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码。

迭代实现：

class Solution {// 定义一个列表来存储遍历的结果List<Integer> list = new ArrayList<>();// 定义一个双端队列来模拟栈，用于迭代中序遍历Deque<TreeNode> que = new LinkedList<>();public List<Integer> inorderTraversal(TreeNode root) {// 调用迭代的中序遍历方法inorder(root);// 返回中序遍历的结果列表return list;}// 迭代的中序遍历方法public void inorder(TreeNode root){// 如果当前节点为空，则返回if(root == null) return;// 当当前节点不为空或双端队列不为空时，执行循环while(root != null || !que.isEmpty()){// 当当前节点不为空时，将其推入双端队列// 并移动到当前节点的左子节点while(root != null){que.push(root);root = root.left;}// 当当前节点为空时，说明左子树已遍历完成// 弹出双端队列的顶部元素，即当前节点的右子节点root = que.pop();// 将弹出的节点的值添加到结果列表list.add(root.val);// 移动到当前节点的右子节点root = root.right;}}
}