树

94.中序遍历

我们使用栈模拟递归，回忆二叉树的中序遍历过程，先把根和他的左子树加入栈中，如果为空就出栈，将出栈的节点值加入结果集，再把右子树加入栈中，重复之前的过程。

 List<Integer> res=new LinkedList<>();
        if(root==null) return res;
        Deque<TreeNode> stack=new ArrayDeque<>();
        while(root!=null||!stack.isEmpty()){
            if(root!=null){
                stack.offerLast(root);
                root=root.left;
            }else{
            root=stack.pollLast();
            res.add(root.val);
            root=root.right;
            }
        }
      return res;
    }