题目描述

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

示例：

输入：root = [1,null,2,3]
输出：[1,3,2]

题目分析

递归：递归左子树 -> 把当前结点加入列表中 -> 递归右子树
迭代：先让当前结点入栈，再处理左子结点，最后处理右子结点

Java

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    ans.addAll(inorderTraversal(root.left));
    ans.add(root.val);
    ans.addAll(inorderTraversal(root.right));
    return ans;
}


public List<Integer> inorderTraversal2(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        ans.add(cur.val);
        cur = cur.right;
    }

    return ans;
}

Kotlin

// 递归
fun inorderTraversal(root: TreeNode?): List<Int> {
    val ans = ArrayList<Int>()
    if (root == null) {
        return ans
    }
    ans.addAll(inorderTraversal(root.left))
    ans.add(root.`val`)
    ans.addAll(inorderTraversal(root.right))
    return ans
}

// 迭代
// 使用栈模拟
fun inorderTraversal2(root: TreeNode?): List<Int> {
    val ans = ArrayList<Int>()
    val stack = LinkedList<TreeNode>()
    var cur = root
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur)
            cur = cur.left
        }
        cur = stack.pop()
        ans.add(cur.`val`)
        cur = cur.right
    }

    return ans
}