二叉樹的前中后遍歷，其前中后，您可理解為指的是根結(jié)點(diǎn)所在的序。

• 前序遍歷：前序遍歷的順序為根-左-右
• 中序遍歷：中序遍歷的順序為左-根-右
• 后序遍歷：后序遍歷的順序為左-右-根

1.前序遍歷

思路：利用棧后進(jìn)先出的特性。

1.根結(jié)點(diǎn)入棧；
2.循環(huán)取棧頂元素、右子結(jié)點(diǎn)入棧、左子結(jié)點(diǎn)入棧。

JAVA參考代碼

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
?
    TreeNode(int val) {
        this.val = val;
    }
}

public List<Integer> preorderTree(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> preorder = new ArrayList<>();
?
    if (root == null) {
        return preorder;
    }
?
    stack.push(root);
    while (!stack.empty()) {
        TreeNode node = stack.pop();
        preorder.add(node.val);
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
?
    return preorder;
}

2.中序遍歷

思路：利用棧后進(jìn)先出的特性。

1.根結(jié)點(diǎn)入棧；
2.所有左子結(jié)點(diǎn)入棧；
3.循環(huán)取出棧頂元素、判斷右子結(jié)點(diǎn)是否為空：
4.為空：取棧頂元素、若當(dāng)前元素為棧頂元素右子樹，彈出丟棄即可；（此時根結(jié)點(diǎn)已被上述訪問取出）
5.不為空：入棧、然后所有子節(jié)點(diǎn)入棧。

JAVA參考代碼

public List<Integer> inorderTree(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> inorder = new ArrayList<>();
?
    while (root != null) {
        stack.push(root);
        root = root.left;
    }
?
    while (!stack.isEmpty()) {
        TreeNode node = stack.peek();
        inorder.add(node.val);
?
        if (node.right == null) {
            node = stack.pop();
            while (!stack.isEmpty() && stack.peek().right == node) {
                node = stack.pop();
            }
        } else {
            node = node.right;
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
    }
    return inorder;
}

3.后序遍歷

思路：借助全局變量，遞歸左子結(jié)點(diǎn)、遞歸右子結(jié)點(diǎn)。

JAVA參考代碼

List<Integer> result = new ArrayList<>();
?
public List<Integer> postorderTree(TreeNode root) {
    TreeNode cur = root;
?
    if(cur == null) {
        return result;
    }
    if(cur.left != null) {
        postorderTree(cur.left);
    }
    if(cur.right != null) {
        postorderTree(cur.right);
    }
    result.add(cur.val);
    return result;
}