用java写中序遍历算法

下面是使用Java编写的二叉树中序遍历算法：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class InorderTraversal {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

在这个算法中，我们使用了一个栈来存储节点。首先将根节点压入栈中，然后将其所有左子结点压入栈中，取出栈顶节点，保存节点值，再将当前指针移到其右子节点上，若存在右子节点，则将右子节点压入栈中，若不存在，则取出栈顶节点，再处理栈顶节点的右子节点。