二叉树的中序遍历

来源Leetcode第94题二叉树的中序遍历

给定一个二叉树，返回它的中序遍历。

中序遍历就是左中右的顺序，就当复习一下数据结构里的内容了。
如果是栈的话，那就是根结点入栈，接着左子树入栈，直到左子树为空，在进行出栈操作，左子树出栈，根结点出栈，右子树入栈。

递归

很经典的递归写法。
代码如下：

class Solution {
      List<Integer> result = new ArrayList<>();
      public List<Integer> inorderTraversal(TreeNode root) {
          midOrder(root);
          return result;
      }

      public void midOrder(TreeNode root){
          if(root != null){
              if(root.left != null)
                  midOrder(root.left);
              result.add(root.val);
              if(root.right != null)
                  midOrder(root.right);
          }
      }
}

栈

代码如下：

public List <Integer> inorderTraversal(TreeNode root) {
    List <Integer> res = new ArrayList < > ();
    Stack <TreeNode> stack = new Stack < > ();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        res.add(current.val);
        current = current.right;
    }
    return res;
}

莫里斯遍历

莫里斯遍历首先需要将二叉树线索化，关于线索二叉树

思路：
记当前遍历的节点为 cur

• cur.left 为 null，保存 cur 的值，更新 cur = cur.right
• cur.left 不为 null，找到 cur.left 这颗子树最右边的节点记做 last
  • last.right 为 null，那么将 last.right = cur，更新 cur = cur.left
  • last.right 不为 null，说明之前已经访问过，第二次来到这里，表明当前子树遍历完成，保存 cur 的值，更新 cur = cur.right

图示及代码参考题解

代码如下：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        //情况 1
        if (cur.left == null) {
            ans.add(cur.val);
            cur = cur.right;
        } else {
            //找左子树最右边的节点
            TreeNode pre = cur.left;
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
            }
            //情况 2.1
            if (pre.right == null) {
                pre.right = cur;
                cur = cur.left;
            }
            //情况 2.2
            if (pre.right == cur) {
                pre.right = null; //这里可以恢复为 null
                ans.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return ans;
}