二叉树的前中后序遍历

二叉树的前中后遍历，其前中后，您可理解为指的是根结点所在的序。

• 前序遍历：前序遍历的顺序为根-左-右
• 中序遍历：中序遍历的顺序为左-根-右
• 后序遍历：后序遍历的顺序为左-右-根

1.前序遍历

思路：利用栈后进先出的特性。

1.根结点入栈；
2.循环取栈顶元素、右子结点入栈、左子结点入栈。

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.中序遍历

思路：利用栈后进先出的特性。

1.根结点入栈；
2.所有左子结点入栈；
3.循环取出栈顶元素、判断右子结点是否为空：
4.为空：取栈顶元素、若当前元素为栈顶元素右子树，弹出丢弃即可；（此时根结点已被上述访问取出）
5.不为空：入栈、然后所有子节点入栈。

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.后序遍历

思路：借助全局变量，递归左子结点、递归右子结点。

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;
}