二叉树的中序遍历：递归法和迭代法

题目：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

对于中序遍历，两种最常用的方法是递归法和迭代法。下面分别给出这两种方法最简洁的 Java 实现，任选其一即可。
中序遍历顺序：左子树 → 根节点 → 右子树
递归法最直观，而迭代法用栈避免递归深度问题。
复杂度：

• 时间：O(n)
  
• 空间：递归 O(h)，迭代 O(h)（h = 树高）
  

一、递归法的 Java 实现：

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {}
8. *     TreeNode(int val) { this.val = val; }
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
17. class Solution {
18.     public List<Integer> inorderTraversal(TreeNode root) {
19.         if(root==null){
20.             // 注意返回结果要List类型，不能 return null
21.             return new ArrayList();
22.         }
24.         List<Integer> res = new ArrayList<>();
25.         inorder(root,res);
26.         return res;
27.     }
28.     public void inorder(TreeNode root, List<Integer> res){
29.         // 注意 左结点或右结点为空，就回到上一层
30.         if(root==null){
31.             return;
32.         }
33.         inorder(root.left, res);   //左
34.         res.add(root.val);         //根
35.         inorder(root.right, res);  //右
36.     }
37. }

复制代码

二、迭代法的 Java 代码：

1. class Solution {
2.     public List<Integer> inorderTraversal(TreeNode root) {
3.         List<Integer> res = new ArrayList<>();
4.         Deque<TreeNode> stack = new ArrayDeque<>();
5.         TreeNode cur = root;
7.         while (cur != null || !stack.isEmpty()) {
8.             while (cur != null) {      // 一路向左
9.                 stack.push(cur);
10.                 cur = cur.left;
11.             }
12.             cur = stack.pop();         // 当前子树最左节点
13.             res.add(cur.val);          // 访问根
14.             cur = cur.right;           // 转向右子树
15.         }
16.         return res;
17.     }
18. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！