我的做法：递归
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
inorder(root, ans);
return ans;
}
public void inorder(TreeNode root, List<Integer> ans) {
if (root == null) return;
inorder(root.left, ans);
ans.add(root.val);
inorder(root.right, ans);
}
}
但是递归存在效率问题。
栈迭代方法虽然提高了效率，但其嵌套循环却非常烧脑，不易理解，容易造成 “一看就懂，一写就废” 的窘况。
而且对于不同的遍历顺序（前序、中序、后序），循环结构差异很大，更增加了记忆负担。
public static List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return list;
}
拓展一种“颜色标记法”
其核心思想如下：
使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。
作者：henry
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/25220/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
白色节点可以认为是TreeNode类型，灰色节点可以认为是Integer类型，不做额外标记。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
Stack<Object> st = new Stack<>();
st.push(root);
while (!st.isEmpty()) {
Object o = st.pop();
// 逆序入栈，中序遍历就是右、中、左
if (o instanceof TreeNode) {
st.push(((TreeNode) o).right);
st.push(((TreeNode) o).val);
st.push(((TreeNode) o).left);
} else if (o instanceof Integer) {
ans.add((Integer) o);
}
}
return ans;
}
}
