前序

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            // 压栈时记录数据
            stack.push(p);
            result.add(p.val);
            // 埋头一直向左走
            p = p.left;
        } else {
            // 走到null节点，出栈
            TreeNode node = stack.pop();
            // 更新p指针指向右节点
            p = node.right;   
        }
    }
    return result;
}

每个节点会访问 3 次，前序遍历时就是当第一次访问该节点时就输出该节点的值。这个序就是指递归序。
前序遍历是一直埋头向左走，走到最后，再出栈，然后将指针 p 指向出栈的节点的右子树，再对右子树进行操作。
前序遍历主要思想是整棵树是可以被左边界的节点分解掉。

记住两个要点：

定义一个指针 p 指向 root。
一直向左走，入栈时添加节点值。

走到左子树尽头，弹出栈顶元素，将 p 指向刚弹出元素的右节点。继续循环步骤 1，直到栈空。

中序

class Solution {
 public List<Integer> inorderTraversal(TreeNode root) {
     List<Integer> res = new LinkedList<>();
     if (root == null) return res;
     Deque<TreeNode> stack = new ArrayDeque<>();
     TreeNode p = root;
     while (!stack.isEmpty() || p != null) {
         while (p != null) {
             stack.addLast(p);
             p = p.left;
         }
         TreeNode node = stack.pollLast();
         res.add(node.val);
         p = node.right;
     }
     return res;
 }
}

思路和前序是差不多的，关键在如下图所示，当指针遇到空节点时，需要进行栈弹出操作，对于中序，弹出操作则记录所弹出节点的数据，对于前序，则是在入栈时记录数据。
二叉树迭代遍历关键点.png

Morris

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)O(1)。
Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 xx）：

如果 xx 无左孩子，先将 xx 的值加入答案数组，再访问 xx 的右孩子，即 x = x.\textit{right}x=x.right。
如果 xx 有左孩子，则找到 xx 左子树上最右的节点（即左子树中序遍历的最后一个节点，xx 在中序遍历中的前驱节点），我们记为 \textit{predecessor}predecessor。根据 \textit{predecessor}predecessor 的右孩子是否为空，进行如下操作。
如果 \textit{predecessor}predecessor 的右孩子为空，则将其右孩子指向 xx，然后访问 xx 的左孩子，即 x = x.\textit{left}x=x.left。
如果 \textit{predecessor}predecessor 的右孩子不为空，则此时其右孩子指向 xx，说明我们已经遍历完 xx 的左子树，我们将 \textit{predecessor}predecessor 的右孩子置空，将 xx 的值加入答案数组，然后访问 xx 的右孩子，即 x = x.\textit{right}x=x.right。
重复上述操作，直至访问完整棵树。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        TreeNode predecessor = null;
        while (root != null) {
            if (root.left != null) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    res.add(root.val);
                    predecessor.right = null;
                    root = root.right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}

后序

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    TreeNode pLastVisit = null;
    // 一直走到最左边
    while (p != null) {
        stack.addLast(p);
        p = p.left;
    }

    while (!stack.isEmpty()) {
        p = stack.pollLast();
        // 判断是否需要输出根节点的值，
        // 输出根节点的值的前提是它的左、右子树都已经完成遍历
        if (p.right == null || p.right == pLastVisit) {
            res.add(p.val);
            // 修改最近一次经过的节点
            pLastVisit = p;
        } else {
            // 左子树刚被访问过，
            stack.addLast(p);
            p = p.right;
            while (p != null) {
                stack.addLast(p);
                p = p.left;
            }
        }
    }

    return res;
}

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> s = new Stack();
        List<Integer> ans = new ArrayList<Integer>();
        TreeNode cur = root;

        while (cur != null || !s.empty()) {
            // 一直埋头向左走
            while (!isLeaf(cur)) {
                s.push(cur);
                cur = cur.left;
            }

            // 走不动了，左节点的值一定是最先加入的，它不会再被遍历
            if (cur != null) ans.add(cur.val);

            while (!s.empty() && cur == s.peek().right) {
                cur = s.pop();
                ans.add(cur.val);
            }

            if (s.empty()) cur = null; else cur = s.peek().right;
        }

        return ans;
    }

    private boolean isLeaf(TreeNode r) {
        if (r == null) return true;
        return r.left == null && r.right == null;
    }
}

后序遍历定义：先左子树、后右子树，再根节点，它的难点在于我们需要跳过根节点，因此需要判断上次访问的节点是位于左子树还是右子树：

位于左子树：需要跳过根节点，走到根节点的右子树，等遍历完右子树后再回到根节点。
位于右子树：直接访问根节点。

递归思维要点

不要人肉进行递归（最大误区）
找到最近最简方法，将其拆解成可重复解决的问题（重复子问题）
数学归纳法思维，

07_算法

二叉树遍历

前序

中序

Morris

后序

递归思维要点