原题链接： https://leetcode.com/problems/binary-tree-inorder-traversal/

1. 题目介绍

Given a binary tree, return the inorder traversal of its nodes’ values. 给定一个二叉树，返回对这个树进行中序遍历的结果。 中序遍历：在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。 Example: Follow up: Recursive solution is trivial, could you do it iteratively? 递归的解法很简单，要不要试一下迭代？

2. 解题思路

2.1 递归

使用递归的方法，每次经过一个节点，都依次将左子树的所有节点、本节点和右子树的所有节点加入List中。最后就可以实现对二叉树的中序遍历。 实现代码

/** * 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) { List<Integer> l = new ArrayList<>(); addIntoList(l,root); return l; } public void addIntoList( List<Integer> l , TreeNode root) { if(root == null){ return; } addIntoList(l , root.left); l.add(root.val); addIntoList(l , root.right); } }

2.2 迭代

中序遍历的顺序是: 1 左子树 2 根节点 3 右子树 因此每遍历到一个节点时，首先要把根节点入栈，然后继续遍历左子树去。 当左子树为空时，暂时先不要弹出栈顶元素，而只是将栈顶元素的 val 值存入List。 之后再将栈顶元素取出，遍历栈顶元素的右子树。 实现代码

/** * 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) { List<Integer> l = new ArrayList<>(); if(root == null){ return l; } TreeNode temp = root; Stack<TreeNode> s = new Stack<>(); while(temp != null || s.isEmpty() != true){ if(temp != null){ s.push(temp); temp = temp.left; }else{ l.add(s.peek().val); temp = s.pop().right; } } return l; } }