二叉树的中序遍历：递归法和迭代法
题目：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。对于中序遍历，两种最常用的方法是递归法和迭代法。下面分别给出这两种方法最简洁的 Java 实现，任选其一即可。
中序遍历顺序：左子树 → 根节点 → 右子树
递归法最直观，而迭代法用栈避免递归深度问题。
复杂度：
[*]时间：O(n)
[*]空间：递归 O(h)，迭代 O(h)（h = 树高）
一、递归法的 Java 实现：
/**
* 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 {
public List<Integer> inorderTraversal(TreeNode root) {
if(root==null){
// 注意返回结果要List类型，不能 return null
return new ArrayList();
}
List<Integer> res = new ArrayList<>();
inorder(root,res);
return res;
}
public void inorder(TreeNode root, List<Integer> res){
// 注意 左结点或右结点为空，就回到上一层
if(root==null){
return;
}
inorder(root.left, res); //左
res.add(root.val); //根
inorder(root.right, res);//右
}
}二、迭代法的 Java 代码：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) { // 一路向左
stack.push(cur);
cur = cur.left;
}
cur = stack.pop(); // 当前子树最左节点
res.add(cur.val); // 访问根
cur = cur.right; // 转向右子树
}
return res;
}
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]