public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1.3 递归实现

public List < Integer > preorderTraversal(TreeNode root) {
    List < Integer > results = new ArrayList < > ();
    preorderRecur(root, results);
    return results;
}

private void preorderRecur(TreeNode root, List < Integer > results) {
    if(root == null) return;
    results.add(root.val);
    preorderRecur(root.left, results);
    preorderRecur(root.right, results);
}

1.4 迭代实现

本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈。

首先我们应该创建一个Stack用来存放节点，首先我们想要打印根节点的数据，此时Stack里面的内容为空，所以我们优先将头结点加入Stack，然后打印。

之后我们应该先打印左子树，然后右子树。所以先加入Stack的就是右子树，然后左子树。
此时你能得到的流程如下:

public List < Integer > preorderTraversal(TreeNode root) {
    List < Integer > results = new ArrayList < > ();
    if(root == null) return results;
    Stack < TreeNode > stack = new Stack < > ();
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        results.add(node.val);
        if(node.right != null) // 先要弹出左子树的节点，所以先将右子树的节点入栈
            stack.push(node.right);
        if(node.left != null) stack.push(node.left);
    }
    return results;
}

2. 中序遍历

对应leetcode 94 题 https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/

2.1 概念

LDR--中序遍历（按照访问左子树——根节点——右子树的方式遍历这棵树）

2.2 递归实现

public List < Integer > inorderTraversal(TreeNode root) {
    List < Integer > results = new ArrayList < > ();
    inorderRecur(root, results);
    return results;
}

private void inorderRecur(TreeNode root, List < Integer > results) {
    if(root == null) return;
    inorderRecur(root.left, results);
    results.add(root.val);
    inorderRecur(root.right, results);
}

2.3 迭代实现

同理创建一个Stack，然后按左中右的顺序输出节点。
尽可能的将这个节点的左子树压入Stack，此时栈顶的元素是最左侧的元素，其目的是找到一个最小单位的子树(也就是最左侧的一个节点)，并且在寻找的过程中记录了来源，才能返回上层,同时在返回上层的时候已经处理完毕左子树了。。
当处理完最小单位的子树时，返回到上层处理了中间节点。（如果把整个左中右的遍历都理解成子树的话，就是处理完左子树->中间(就是一个节点)->右子树）
如果有右节点，其也要进行中序遍历。

当整个左子树退栈的时候这个时候输出了该子树的根节点 2，之后输出中间节点 1。然后处理根节点为3右子树。

public static List < Integer > inorderTraversal2(TreeNode root) {
    List < Integer > results = new ArrayList < > ();
    if(root == null) return results;
    Stack < TreeNode > stack = new Stack < > ();
    TreeNode cur = root;
    while(!stack.isEmpty() || cur != null) {
        // 找到最左子树
        while(cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        results.add(cur.val);
        cur = cur.right;
    }
    return results;
}

3. 后序遍历

对应leetcode 145 题 https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

3.1 概念

LRD--后序遍历（按照访问左子树——右子树——根节点的方式遍历这棵树）

3.2 递归实现

public List < Integer > postorderTraversal(TreeNode root) {
    List < Integer > results = new ArrayList < > ();
    postorderRecur(root, results);
    return results;
}

private void postorderRecur(TreeNode root, List < Integer > results) {
    if(root == null) return;
    postorderRecur(root.left, results);
    postorderRecur(root.right, results);
    results.add(root.val);
}

3.3 迭代实现

public List < Integer > postorderTraversal2(TreeNode root) {
    List < Integer > results = new ArrayList < > ();
    if(root == null) return results;
    Stack < TreeNode > stack = new Stack < > ();
    TreeNode cur = root;
    TreeNode pre = null; //pre节点用于记录前一次访问的节点
    while(!stack.isEmpty() || cur != null) {
        while(cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.peek();
        if(cur.right == null || cur.right == pre) { // 若右节点为空 或右节点访问过
            results.add(cur.val);
            pre = cur;
            stack.pop();
            cur = null; // 此时下一轮循环不要将左子树压栈，直接判断栈顶元素
        } else {
            cur = cur.right;
        }
    }
    return results;
}

码农公寓

1. 前序遍历

1.1 概念

1.2 建立TreeNode模型