二叉树的中序遍历（非递归）

思想：
借助栈，入栈循序：右根左（即中序遍历反过来）；然后借助visit标记；如标记过则添加进结果；否则，则标记下，入栈

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.HashMap;
import java.util.LinkedList;
import java.util.ArrayList;
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null) {
            return res;
        }
        HashMap<TreeNode,Boolean> map = new HashMap<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        map.put(root,false);
        stack.add(root);
        while(stack.size()>0) {
            TreeNode node = stack.pollLast();
            if(map.get(node)==true) {
                res.add(node.val);
            }else {
                if(node.right!=null) {
                    stack.add(node.right);
                    map.put(node.right,false);
                }
                stack.add(node);
                map.put(node,true);
                if(node.left!=null) {
                    stack.add(node.left);
                    map.put(node.left,false);
                }
            }
        }
        return res;
    }
}