二叉树的遍历

递归：

//先序遍历
void preOrder(Node *root) {
    if (root == NULL) {
        return;
    }
    printf("%d\n", root->data);
    preOrder(root->lchild);
    preOrder(root->rchild);
}

//中序遍历
void inOrder(Node *root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->lchild);
    printf("%d\n", root->data);
    inOrder(root->rchild);
}

//后序遍历
void postOrder(Node *root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->lchild);
    postOrder(root->rchild);
    printf("%d\n", root->data);
}

//层次遍历
void levelOrder(Node *root) {
    queue<Node *> q;
    q.push(root);
    while (!q.empty()) {
        Node *now = q.front();
        q.pop();
        printf("%d\n", now->data);
        if (now->lchild != NULL) {
            q.push(now->lchild);
        }
        if (now->rchild != NULL) {
            q.push(now->rchild);
        }
    }
}

非递归：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode top = stack.poll();
            res.add(top.val);
            if (top.right != null) {
                stack.push(top.right);
            }
            if (top.left != null) {
                stack.push(top.left);
            }
        }
        return res;
    }

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

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == pre) {
                res.add(root.val);
                pre = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

无论是先序遍历序列还是后序遍历序列还是层次遍历序列，都必须知道中序遍历序列才能唯一确定一棵树。

例1

给定一棵二叉树的先序遍历序列和中序遍历序列，重建这棵二叉树。
分析：

#include <cstdio>

using namespace std;

const int maxn = 100;

//二叉树存储结构
struct Node {
    int data;
    Node *lchild;
    Node *rchild;
};

int pre[maxn], in[maxn];

Node *create(int preL, int preR, int inL, int inR) {
    if (preL > preR) {
        return NULL;
    }
    Node *root = new Node;
    root->data = pre[preL];
    int k;
    //在中序序列中找到根结点位置
    for (k = inL; k <= inR; k++) {
        if (in[k] == pre[preL]) {
            break;
        }
    }
    int numLeft = k - inL;//左子树结点个数
    root->lchild = create(preL + 1, preL + numLeft, inL, k - 1);
    root->rchild = create(preL + numLeft + 1, preR, k + 1, inR);
    return root;
}

1020 Tree Traversals

1086 Tree Traversals Again

1102 Invert a Binary Tree