LeetCode——二叉树的前中后三种遍历

记录一下二叉树的前序遍历、中序遍历、后序遍历。

NO.94 中序中等 NO.144 前序中等 NO.145 后序困难

这三种遍历有一个共同特点：都是深搜的一种形式。

思路一：迭代实现

以中序遍历为例，实现之后，对于前序和后序就是调整节点访问顺序即可。

不断地向左节点深搜，借助栈结构，将当前节点入栈。直至左节点为空，弹出栈顶节点，保存节点值，并将弹出的节点不断向左节点深搜并保存每个节点。。。

中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    //当栈不为空，或者节点不为空，就继续遍历
    while (!stack.isEmpty() || root != null) {
        if (root != null) {//节点不为空，入栈，向左节点深搜
            stack.add(root);
            root = root.left;//左
        } else {//左节点为空，即深搜触底。出栈一个元素
            TreeNode pop = stack.pop();
            res.add(pop.val);//根
            root = pop.right;//右
        }
    }
    return res;
}

前序遍历

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        if (root != null) {
            stack.add(root);
            res.add(root.val);//根
            root = root.left;//左
        } else {
            TreeNode pop = stack.pop();
            root = pop.right;//右
        }
    }
    return res;
}

后序遍历

后序遍历的迭代实现稍有不同。记录两个较为朴素通用的方法：

转换问题，将后序遍历的左右根的顺序，看作是根右左的翻转。根右左从哪里来？前序遍历的根左右，调整左右的压栈顺序即可得到。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        if (root != null) {
            stack.push(root);
            res.add(root.val);//根
            root = root.right;//右
        } else {
            TreeNode pop = stack.pop();
            root = pop.left;//左
        }
    }
    //得到根右左的序列，翻转得到后序遍历的左右根
    Stack<Integer> s = new Stack<>();
    for (Integer e : res) s.push(e);
    res.clear();
    while (!s.isEmpty()) res.add(s.pop());
    return res;
}

依然采用栈来模拟，但是比前序和中序要麻烦一些。比如中序遍历，当左子树遍历完毕，可以将根弹出然后去遍历右子树即可。

但是后序遍历中左子树遍历完毕，不能立刻将根pop而是peek出根，然后去遍历右子树，只有当右子树也遍历完毕才能弹出根。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    //用set记录访问过的节点
    Set<TreeNode> set = new HashSet<>();
    TreeNode cur = root;
    while (!stack.isEmpty() || root != null) {
        //节点不为空且没有被访问过，入栈
        while (cur != null && !set.contains(cur)) {
            stack.push(cur);
            cur = cur.left;//左
        }
        //遍历完左子树,peek根节点
        cur = stack.peek();
        //如果cur的右子树为空，或者第二次访问节点
        if (cur.right == null || set.contains(cur)) {
            //记录根节点，并弹出
            res.add(cur.val);
            set.add(cur);
            stack.pop();
            //如果栈不空，继续检查遍历下一个栈顶元素的右子树
            if (stack.isEmpty()) return res;
            cur = stack.peek().right;
        } else {//右子树不为空并且第一次访问,遍历右子树
            set.add(cur);
            cur = cur.right;//右
        }
    }
    return res;
}

思路二：递归实现

递归的思路是借助递归栈。

中序遍历

List<Integer> res = new ArrayList<>();

public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) return res;
    dfs(root);
    return res;
}

private void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);//左
    res.add(root.val);//中
    dfs(root.right);//右
}

前序遍历

List<Integer> res = new ArrayList<>();

public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null) return res;
    dfs(root);
    return res;
}

private void dfs(TreeNode root) {
    if (root == null) return;
    res.add(root.val);//根
    dfs(root.left);//左
    dfs(root.right);//右
}

后序遍历

List<Integer> res = new ArrayList<>();

public List<Integer> postorderTraversal(TreeNode root) {
    if (root == null) return res;
    dfs(root);
    return res;
}

private void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);//左
    dfs(root.right);//右
    res.add(root.val);//根
}

ps：都是完成一次遍历，时间复杂度O(n)，空间上取决于树的高度(深度)。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.94 中序 中等 NO.144 前序 中等 NO.145 后序 困难

思路一：迭代实现

中序遍历

前序遍历

后序遍历

思路二：递归实现

中序遍历

前序遍历

后序遍历

NO.94 中序中等 NO.144 前序中等 NO.145 后序困难