二叉树的中序遍历

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),因为用的是递归的方法，需要空间来维护栈的调用。题目中说递归的算法很简单，你能不能用迭代来实现呢？

我们接下来考虑一下怎么使用迭代来实现。使用迭代的话，就是将递归的栈，我们自己来维护。这里找了一个图

来自动画演示+三种实现 94. 二叉树的中序遍历

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，祝你升职、加薪、不提桶！