二叉树的中序遍历
WangScaler: 一个用心创作的作者。声明：才疏学浅，如有错误，恳请指正。
题目
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
初步分析
中序遍历即是左根右。那么有左子树，就持续递归到最左边的叶子节点，再拿到根节点，再递归右子树。将遍历的数放到list里面。
例如此图，根节点1没有左子树，则直接把1放入。递归右子树2，3。当右子树根节点2有左子树的时候，继续递归3，发现3没有，则放入列表。再把根节点2放入。所以最后的顺序是1，3，2。
也就是左子树递归计算，放入根节点，右子树递归计算。本例中第一次递归拆分成1、【2、3】，第二次递归拆分成2、3。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root==null){
return list;
}
return traversal(root,list);
}
public static List<Integer> traversal(TreeNode root,List<Integer> list) {
if(root==null){
return list;
}
traversal(root.left,list);
list.add(root.val);
traversal(root.right,list);
return list;
}继续分析
这个递归的时间复杂度是O(n)会遍历所有的节点。空间复杂度也是O(n),因为用的是递归的方法，需要空间来维护栈的调用。题目中说递归的算法很简单，你能不能用迭代来实现呢？
我们接下来考虑一下怎么使用迭代来实现。使用迭代的话，就是将递归的栈，我们自己来维护。这里找了一个图
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stk = new LinkedList<TreeNode>();
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
list.add(root.val);
root = root.right;
}
return list;
}当我们左子树不为空的时候，我们持续迭代，将左子树入栈。原理和使用递归的方法是一样的。上述的方法的空间复杂度都是O(n),我们有没有办法不使用栈来解决这个问题呢？
- 根节点无左子树，那么直接将x加入答案数组，接下来就是处理x的右子树
根节点有左子树，我们找到左子树的中序遍历的最后一个节点（左子树上的最右侧的节点）
- 如果无右子树。则将其右子树指向根节点。
如果有右子树
- 判断是否为根节点，是的话，则证明遍历完，讲右子树置为空，将根节点加入答案，继续访问根节点的右子树。
- 不是根节点的话，则继续遍历右子树。
答案
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
TreeNode newTree = null;
while (root != null) {
if (root.left != null) {
newTree = root.left;
while (newTree.right != null && newTree.right != root) {
newTree = newTree.right;
}
if (newTree.right == null) {
newTree.right = root;
root = root.left;
}
else {
list.add(root.val);
newTree.right = null;
root = root.right;
}
}
else {
list.add(root.val);
root = root.right;
}
}
return list;
}复杂度
- 时间复杂度: O(n)
- 空间复杂度：O(1)
总结
看了答案，可能大家也都不明白最后这种Morris 中序遍历的方法，接下来我图解以下。起初是这样的。
注：红色表示根节点，蓝色表示第二层while循环的过程。黑线表示左子树，绿色表示右子树
第一次循环
3的左子树不为空，将左子树作为新的树的根节点newTree = root.left;当右子树不为空或者不为根节点的时候，持续循环直到循环到无右子树时。
while (newTree.right != null && newTree.right != root) {
newTree = newTree.right;
}
将其右子树，变为根节点。
第二次循环
第一次循环结束时root = root.left;，所以以1为根节点做遍历
同第一次循环将2的右子树指向原来的根节点1
第三次循环
此次2做根节点
无左右子树，加入把2加入list，根节点变为右子树root = root.right;
第四次循环
root节点又回到1。
但此次循环，2的右子树不为空且为根节点，此时则认为以1为根节点的左子树遍历完毕，所以
else {
list.add(root.val);
newTree.right = null;
root = root.right;
}
将1的值加入list。把newtree的右子树置为空。根节点转为4。
第五次循环
4为根节点，没有左子树，所以直接将4加入list，根节点转为3
第六次循环
遍历到4，发现4的右节点为根节点，则认为根节点3左子树所有节点遍历完毕
则将3加入list。将4的右子树置为null。根节点转为右子树
根节点3的右子树为空，则遍历结束。
返回list。即【2，1，4，3】
这个算法不容易理解，将最右侧的指针指向根节点的目的就是为了记录根节点的位置，以便遍历完左子树之后回到之前的位置。也就是说中序遍历时左根右。左子树遍历完会回到根节点，左子树的中序遍历的最后一个树书，一定在他右子树的最后一个叶子节点，我们只需要将这个叶子节点指向根节点，那么我们遍历完左子树，就能回到根节点。
还不明白的多看几遍图解再理解理解吧。
都来了，点个赞再走呗！关注WangScaler，祝你升职、加薪、不提桶！
