94.二叉树的中序遍历(二叉树，简单)

题目链接

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

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

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

示例 5：

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

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解答

/**
 * 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) {
        /*// 递归实现
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            result.addAll(inorderTraversal(root.left));
            result.add(root.val);
            result.addAll(inorderTraversal(root.right));
        }
        return result;*/
        // 迭代实现
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> nodesStack = new Stack<>();
        nodesStack.push(root);
        TreeNode node;
        boolean isPopOut = false;   // 记录上一轮循环进行的是入栈还是出栈操作
        while (!nodesStack.isEmpty()) {
            if (!isPopOut) {
                // 上轮循环为入栈操作，本轮继续入栈
                if ((node=nodesStack.peek()) != null) {
                    // 栈顶元素不为空，仍可继续入栈后续元素
                    nodesStack.push(node.left);
                } else {
                    // 栈顶元素为空，则上轮循环中的栈顶元素的左子树为空，不需要对其左子树进行中序遍历
                    nodesStack.pop();
                    isPopOut = true;
                }
            } else {
                // 上轮循环为出栈操作，说明当前栈顶元素的左子树已完成中序遍历。
                // 先将本轮循环的栈顶元素出栈，再将其右子树入栈
                node = nodesStack.pop();
                result.add(node.val);
                nodesStack.push(node.right);
                isPopOut = false;
            }
        }
        return result;
    }
}