题目：通过率 21.8% 难度：中等

描述：

给定一个 二叉树 ，返回它的中序 遍历。

进阶: 递归算法 很简单，你可以通过迭代算法完成吗？

代码模板

解题思路：

中序遍历 （LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，先左后根再右。巧记：左根右。

如图中序遍历结果为：DBEAFC

题中说明了 要求使用 迭代法

使用一个栈来存储二叉树节点，根据中序遍历的规则，我们可以推算出这样的规律：

1. 将当前非空节点入栈

2. 如果左子节点不为空，则继续将左子节点入栈

3. 如果左子节点为空，则抛出栈顶节点并记录 val 值，然后将其右子节点入栈

4. 重复 1、2、3 步骤直至栈空

代码：

源代码：

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right ;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public List< Integer > inorderTraversal(TreeNode root) {

Stack<TreeNode> stack = new Stack<TreeNode>();

ArrayList<Integer> result = new ArrayList<Integer>();

TreeNode curt = root;

while (curt != null || !stack.empty()) {

while (curt != null) {

stack.add(curt);

curt = curt.left;

}

curt = stack.pop();

result.add(curt.val);

curt = curt.right;

}

return result;

}

}

运行结果：