一、leetcode算法
1、二叉树的中序遍历
1.1、题目
给定一个二叉树的根节点 root ，返回它的中序遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[2,1]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
1.2、思路
思路一：此题我们可以使用Morris中序遍历来解决问题，首先有以下规则我们需要熟记于心
假设当前遍历到的节点为 x
1.如果x无左孩子，先将x的值加入答案数组，再访问x的右孩子，即x=x.right;
2.如果x有左孩子，则找到x左子树上最右的节点（即左子树一直向右找到最后一个为止），我们记为predecessor。根据predecessor的右孩子是否为空，进行下面的规则。
3.如果predecessor的右孩子为空，则将其右孩子指向x，然后访问x的左孩子，即x=x.left。
4.如果predecessor的右孩子不为空，则此时其右孩子指向x，说明我们已经遍历完x的左子树，我们将predecessor的右孩子置空，将x的值加入答案数组，然后访问x的右孩子，即x=x.right;
1.3、答案
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); TreeNode predecessor = null; while(root != null){ //如果 x 有左孩子，则找到 x 左子树上最右的节点 if(root.left != null){ //predecessor节点就是当前root节点向左走一步，然后一直向右走到头 predecessor = root.left; while(predecessor.right != null && predecessor.right != root){ predecessor = predecessor.right; } /** 这里开始判断predecessor节点的情况如果predecessor 的右孩子为空，则将其右孩子指向 x，然后访问 x 的左孩子, 即 x =x.left */ if(predecessor.right == null){ predecessor.right = root; root = root.left; } /** 如果 predecessor 的右孩子不为空，则此时其右孩子指向 x，说明我们已经遍历完 x 的左子树，我们将predecessor 的右孩子置空，将 x 的值加入答案数组，然后访问 x 的右孩子，即 x =x.right。 */ else{ res.add(root.val); predecessor.right = null; root = root.right; } } //如果 x 无左孩子，先将 x 的值加入答案数组，再访问 x 的右孩子，即 x =x.right。 else{ res.add(root.val); root = root.right; } } return res; } }
复杂度分析
时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 O(2n)=O(n)。
空间复杂度：O(1)。
