题目

• 概述：给定一个二叉树，返回它的中序遍历

  要求：使用非递归算法

• 输入：二叉树的根节点

• 输出：中序遍历的值列表

• 出处：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

思路

• 规律：

1. 查找第一个结点：由于中序遍历的顺序是：左子树->根->右子树，所以

   1. 如果根节点的左子树不为空，则第一个结点必定在该左子树中
   2. 如果该左子树为空，则第一个结点就是根节点

2. 查找第二个结点：由于第一个结点的左子树必为空，所以

   1. 如果第一个结点的右子树不为空，则第二个结点必定在该右子树中，按照查找第一个结点的规律可以从该右子树中查找到第二个结点
   2. 如果该右子树为空，则第二个结点必定为第一个结点的根节点（如果第一个结点的根节点存在的话）

3. 依次类推可以查找到所有结点

• 具体做法：

• 由于需要从左子树回退到根，所以考虑用栈来存储从根节点到第一个结点中经过的结点

• 首先将根节点入栈

• 重复观察栈顶元素直至栈为空

  1. 如果栈顶元素的左孩子为空或者已被访问过，则将栈顶元素出栈，放入中序遍历列表中

     1. 如果栈顶元素的右孩子为空，标记左孩子已被访问过

     2. 如果栈顶元素的右孩子不为空，则将栈顶元素的右孩子入栈，标记左孩子未被访问过

  2. 如果栈顶元素的左孩子不为空，则将栈顶元素的左孩子入栈，标记左孩子未被访问过

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        
        if (root == null) {
            return result;
        }
        
        boolean leftVisited = false;
        TreeNode top;
        stack.push(root);
        while (!stack.isEmpty()) {
            top = stack.peek();
            if (top.left == null || leftVisited) {
                result.add(top.val);
                stack.pop();
                if (top.right == null) {
                    leftVisited = true;
                } else {
                    stack.push(top.right);
                    leftVisited = false;
                }
            } else {
                stack.push(top.left);
                leftVisited = false;
            }
        }
        return result;
    }
}