力扣94题（java语言）

题目 

思路

使用一个栈来模拟递归的过程，以非递归的方式完成中序遍历(使用栈可以避免递归调用的空间消耗)。

遍历顺序步骤：

1. 遍历左子树
2. 访问根节点
3. 遍历右子树

package algorithm_leetcode;  import java.util.ArrayList; import java.util.List; import java.util.Stack;  public class Solution_94 { 	public List<Integer> inorderTraversal(TreeNode root) { 		// 待处理节点 		Stack<TreeNode> stack = new Stack<>(); 		// 结果 		List<Integer> output_arr = new ArrayList<>(); 		 		// 如果root为空 		if (root == null) { 			// 返回空的 output_arr 			return output_arr; 		} 		 		// 初始化为根节点 		TreeNode current = root; 		 		// 循环 只要当前节点不为空，并且栈不为空  		while (current != null || !stack.isEmpty()) { 			// 当前节点不为空，直到左子树为空 			while (current != null) { 				// 添加到栈 				stack.push(current); 				// 当前节点移动到左子节点 				current = current.left; 			} 			// 弹出栈节点 			current = stack.pop(); 			// 添加到结果中 			output_arr.add(current.val); 			// 如果有右子节点，就移动到右子节点 			current = current.right; 		} 		 		return output_arr; 		 	} }  class TreeNode {     int val;     TreeNode left;     TreeNode right;     TreeNode() {}     TreeNode(int val) { this.val = val; }     TreeNode(int val, TreeNode left, TreeNode right) {         this.val = val;         this.left = left;         this.right = right;     } }