模版代码
public class PreorderTraversal { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); // 1. 初始化辅助节点curr Stack<TreeNode> tempStack = new Stack<>(); TreeNode curr = root; // 2. 通过循环遍历树 while (!tempStack.empty() || null != curr) { if (null != curr) { tempStack.push(curr); result.add(curr.val); curr = curr.left; } if (null == curr) { // 如果下一次循环中 curr 也为空，则表示对于本次弹出后的栈，其栈顶节点左子树已经遍历完毕了，仍然是弹出栈顶节点并对其右子树遍历 curr = tempStack.pop().right; } } return result; } } 中序遍历访问顺序：左 → 根 → 右
递归实现递归代码和前序遍历类似，只是这里我们需要先递归访问到整棵树的最左叶节点
public class InorderTraversal { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); _inorderTraversal(root, result); return result; } private void _inorderTraversal(TreeNode node, List<Integer> result) { if (null != node) { _inorderTraversal(node.left, result); // 输出完左孩子就输出根节点，之后再处理右孩子 result.add(node.val); _inorderTraversal(node.right, result); } } } 非递归实现实现思路
同样的，我们使用栈(Stack)来实现树的中序遍历，我们需要牢记中序遍历的顺序是「左-根-右」。也就是在打印当前节点之前，要保证该节点的左子树不存在或已经遍历完毕，所以我们同样需要一个『辅助节点 curr』来保存「正在访问的节点信息」，在循环开始时保证它指向栈顶节点的左孩子，在 curr 为null时我们便认为栈顶元素的左子树已无需遍历, 而循环跳出条件也需要变成当前栈非空或 curr 非空。
预处理：将辅助节点 curr 初始化为根节点
通过循环遍历树
将当前节点 curr 的所有左孩子节点压入栈
弹出栈顶的元素，让 curr 指向该元素并输出
让当前节点 curr 指向其自身的右孩子
参考代码
public class InorderTraversal { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); Stack<TreeNode> tempStack = new Stack<>(); TreeNode curr = root; while (null != curr || !tempStack.empty()) { while (null != curr) { tempStack.push(curr); curr = curr.left; } // 此时可以保证栈顶元素不存在左子树，弹出并输出，最后再对其右孩子节点进行迭代判定 curr = tempStack.pop(); result.add(curr.val); curr = curr.right; } return result; } }便于记忆的模版代码
实现思路
预处理：将辅助节点初始化为根节点
通过循环实现遍历
既然是模版，那么形式上和之前前序遍历的模版是类似的，不同的仅是对于辅助节点 curr 是否为null的两种情况的处理：
当前节点curr 存在，此时将 curr 压入栈之后仅让 curr 指向其左孩子
当前节点curr 为null，此时栈顶元素的左子树为空，我们将栈顶元素弹出并输出，然后让当前节点 curr 指向其右孩子
模版代码
public class InorderTraversal { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); Stack<TreeNode> tempStack = new Stack<>(); TreeNode curr = root; while (null != curr || !tempStack.empty()) { if (null != curr) { tempStack.push(curr); curr = curr.left; } if (null == curr) { curr = tempStack.pop(); result.add(curr.val); // 如果当前节点curr是叶子节点，则curr的右孩子一定为null，下次循环时会再次弹出栈顶元素(也就是当前访问节点curr的根节点)进行输出 curr = curr.right; } } return result; } } 后序遍历访问顺序：左 → 右 → 根
递归实现在后序遍历时，我们需要先访问整棵树的最左子节点，再访问与这个最左子节点根节点的右节点
参考代码
public class postorderTraversal { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); _postorderTraversal(root, result); return result; } private void _postorderTraversal(TreeNode node, List<Integer> result) { if (null != node) { _postorderTraversal(node.left, result); _postorderTraversal(node.right, result); // 输出了左孩子和右孩子之后，才输出根节点 result.add(node.val); } } } 非递归实现实现思路