题解 | #二叉树的中序遍历# 非递归实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     *	不断遍历左节点，同时压入栈，当没有左节点的时候证明到底了，可以将栈顶元素弹出放入集合
	 *	然后判断弹出元素的右节点，方法都是一样，不断循环这个过程，就可以完成中序遍历
     *	注意结束条件是当前节点和队列都为空时
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] inorderTraversal (TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();
        TreeNode curr = root;
        while(curr != null || !stack.isEmpty()){
            if(curr != null){
                stack.push(curr);
                curr = curr.left;
            }else{
                TreeNode pop = stack.pop();
                list.add(pop.val);
                curr = pop.right;
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}