算法题二叉树的中序遍历：每天一算法树

算法题二叉树的中序遍历：每天一算法树进阶: 递归算法很简单，你可以通过迭代算法完成吗？给定一个二叉树，返回它的中序 遍历。刻意练习并不意味着寻找答案并记住它，这种练习方法不是长久之计。 在没有参考答案情况下，越能自主解决问题，才越能提高自身能力。题目：通过率 21.8% 难度：中等描述：

点击上方"java全栈技术"关注我们，每天学习一个java知识点

最近整理了一些经典面试题目清单，将帮助您掌握算法及数据结构，并提高您的编程能力。

编程能力就像任何其他技能一样，也是一个可以通过刻意练习提高的。

大多数经典面试题目都有多种解决方案。 为了达到最佳的练习效果，强烈建议您至少将题目练习两遍，如果可以的话，三遍会更好。

刻意练习并不意味着寻找答案并记住它，这种练习方法不是长久之计。 在没有参考答案情况下，越能自主解决问题，才越能提高自身能力。

题目：通过率 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;

}

}

---

运行结果：