二叉树先序遍历和中序遍历,二叉树中序遍历过程
中序遍历，是二叉树遍历的一种。在二叉树中，中序遍历首先遍历左子树，然后遍历根节点，最后遍历右子树。
递归遍历法 public List<Integer> getLDRMethod1(TreeNode treeNode) { List<Integer> result = new ArrayList<>(); if (treeNode != null) { result.addAll(getLDRMethod1(treeNode.left)); result.add(treeNode.val); result.addAll(getLDRMethod1(treeNode.right)); } return result;}递归遍历法就像概述中二叉树定义的一种实现，首先遍历左子树，然后遍历根节点，最后遍历右子树。这种方法一般用来求中序遍历结果，因为递归遍历过程中，方法参数过多本身也是一种资源浪费，而只传递节点的话又不好计算各种累加问题，因此该方法在算法中，能用到场景较少。如果一定要用，也可以通过全局变量的方式来完成。
迭代法 public List<Integer> getLDRMethod(TreeNode treeNode) { List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || treeNode != null) { while (treeNode != null) { stack.add(treeNode); treeNode = treeNode.left; } treeNode = stack.pop(); result.add(treeNode.val); treeNode = treeNode.right; } return result;}该迭代方法需要使用栈来保存还未遍历的节点，遍历思路也比较简单，一直向左遍历，模拟先遍历左子树这一步。如果左为空，就记录该节点值，模拟遍历根节点这一步，然后向右遍历，模拟遍历右子树这一步，一直循环到遍历完所有节点。该方法在算法中经常使用，无论是计算累加问题，还是判断问题，相比递归方法更高效和容易理解，也不需要使用全局变量，唯一的缺点就是需要引入新的栈空间，记录还没有遍历的节点。
Morris中序遍历 public List<Integer> getLDRMethod3(TreeNode treeNode) { List<Integer> result = new ArrayList<>(); TreeNode predecessor = null; while (treeNode != null) { if (treeNode.left != null) { predecessor = treeNode.left; while (predecessor.right != null && predecessor.right != treeNode) { predecessor = predecessor.right; } if (predecessor.right == null) { predecessor.right = treeNode; treeNode = treeNode.left; } else { predecessor.right = null; result.add(treeNode.val); treeNode = treeNode.right; } } else { result.add(treeNode.val); treeNode = treeNode.right; } } return result;}看名字就知道该方法是一个比较难理解的方法。难理解的方法又是相对比较高效的方法：Morris遍历是一个不需要使用栈，仅仅使用一个局部变量就可以完成中序遍历的高效方法。在讲解代码之前，我先简单介绍Morris中序遍历的大致解决理念：
Morris方法使每个节点的右指针都指向中序遍历的下一个节点有了理念1，我们也可以说，每次指向right的时候，就是遍历的时候那么它具体是怎么做的呢：
假设根节点A的左子树B没有右子树，那么B的右子树就是A。假设根节点A的左子树B有右子树，那么就一直向右遍历，直到它没有右子树，设置它的右子树为A上述方案确定A的左子树中序遍历最后一个节点 的 right 指向它自己，也就是保证左子树遍历完成后，遍历根节点。左子树遍历完有两种情况：
左子树为空，说明这个节点没有左子树，当然也可以理解为左子树已经遍历完了左子树的右节点递归最终指向自己，说明它的左子树已经遍历完成了，同时删掉这个右指针，维护树结构。带着这些结论我们来解释上述方法的工作原理：
如果左子树为空，直接遍历该节点，进入右子树。如果左子树不为空，取它的左子树节点，递归该节点的右指针，直到为空设置该节点的右指针指向父节点，表示父节点的左子树遍历完成后，最后一个几点的right指向它。如果该节点的右指针已经指向父节点了，说明该父节点的左子树已经遍历完了，删除这个新加的right标记，遍历该节点，进入右子树