力扣 94 二叉树的中序遍历

题意：中序遍历树

思路：用stack实现树的中序遍历非递归，具体见代码

思想：树的中序遍历

复杂度：时间O（n)，空间O(n)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        HashSet<TreeNode> set = new HashSet();
        List<Integer> res = new ArrayList();
        if(root == null)
            return res;
        
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.peek();
            while(cur.left != null && !set.contains(cur.left)) {
                stack.push(cur.left);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            set.add(cur);
            if(cur.right != null)
                stack.push(cur.right);
        }
        
        return res;
    }
}