方法一：递归
遍历即从跟开始，递归的先访问左节点再访问右节点。中序遍历在访问完左节点后访问该节点的值。
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 public List<Integer> inorderTraversal(TreeNode root) { 18 List<Integer> list = new ArrayList<Integer>(); 19 inOrder(root,list); 20 return list; 21 } 22 public void inOrder(TreeNode root,List<Integer> res){ 23 if(root == null) return; 24 inOrder(root.left,res); 25 res.add(root.val); 26 inOrder(root.right,res); 27 } 28 }
方法二：迭代
递归时由系统隐形的维护一个栈存放每次递归的数据，迭代则由自己维护一个栈来存放每次访问的节点。先通过循环找到整个二叉树的最左节点，并将其路径上的节点放入栈内，最左节点的left一定为空，此时节点root为空，则将栈顶元素出栈赋值给root，访问当前root，然后访问root的right，依次迭代，当左右都为空时则表示当前节点访问完毕，则继续出栈访问前一个节点，当节点为空且栈内没有元素时即访问完成。
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 public List<Integer> inorderTraversal(TreeNode root) { 18 List<Integer> res = new ArrayList<>(); 19 Deque<TreeNode> stack = new LinkedList<>(); 20 while(root != null || !stack.isEmpty()){ 21 while(root != null){ 22 stack.push(root); 23 root = root.left; 24 } 25 root = stack.pop(); 26 res.add(root.val); 27 root = root.right; 28 } 29 return res; 30 } 31 }
方法三：Morris中序
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
1 class Solution { 2 public List<Integer> inorderTraversal(TreeNode root) { 3 List<Integer> res = new ArrayList<Integer>(); 4 TreeNode predecessor = null; 5 6 while (root != null) { 7 if (root.left != null) { 8 // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止 9 predecessor = root.left; 10 while (predecessor.right != null && predecessor.right != root) { 11 predecessor = predecessor.right; 12 } 13 14 // 让 predecessor 的右指针指向 root，继续遍历左子树 15 if (predecessor.right == null) { 16 predecessor.right = root; 17 root = root.left; 18 } 19 // 说明左子树已经访问完了，我们需要断开链接 20 else { 21 res.add(root.val); 22 predecessor.right = null; 23 root = root.right; 24 } 25 } 26 // 如果没有左孩子，则直接访问右孩子 27 else { 28 res.add(root.val); 29 root = root.right; 30 } 31 } 32 return res; 33 } 34 }