二叉树的前中后序遍历

发表于 | 分类于 | 本文总阅读量 次
字数统计: 523 | 阅读时长 ≈ 2

前言

汇总二叉树的前, 中, 后序遍历.每种遍历都有经典的递归和迭代方法.

前序遍历

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorderTraversal(TreeNode root) {

    List<Integer> res = new ArrayList<>();
    helper(root, res);
    return res;
}

private void helper(TreeNode root, List<Integer> res) {
    if (root != null) {
        res.add(root.val);
        if (root.left != null)
            helper(root.left, res);
        if (root.right != null)
            helper(root.right, res);
    }
}

迭代方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> preorderTraversal(TreeNode root) {

    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null)
        return res;

    TreeNode curNode = root;
    stack.push(curNode);
    while (!stack.isEmpty()) {
        curNode = stack.pop();
        res.add(curNode.val);
        if (curNode.right != null)
            stack.add(curNode.right);
        if (curNode.left != null)
            stack.add(curNode.left);
    }
    return res;
}

中序遍历

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    private void helper(TreeNode root, List<Integer> res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }

迭代方法

图解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> inorderTraversal2(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;

    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }

        cur = stack.pop();
        res.add(cur.val);
        cur = cur.right;
    }
    return res;
}

后序遍历

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> postorderTraversal(TreeNode root) {

    List<Integer> res = new ArrayList<>();
    helper(root, res);
    return res;
}

private void helper(TreeNode root, List<Integer> res) {

    if (root != null) {
        if (root.left != null)
            helper(root.left, res);
        if (root.right != null)
            helper(root.right, res);
        res.add(root.val);
    }
}

迭代方法

  1. 前序遍历的过程是中左右。
    • 将其转化成中右左。也就是压栈的过程中优先压入左子树，再压入右子树。
  2. 然后将这个结果反过来，用addFirst()方法将元素输出到数组即可完成逆序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> postorderTraversal(TreeNode root) {

    LinkedList<Integer> res = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();

    if (root == null)
        return res;
    stack.add(root);

    while (!stack.isEmpty()) {
        TreeNode curNode = stack.pop();
        res.addFirst(curNode.val);

        if (curNode.left != null)
            stack.add(curNode.left);
        if (curNode.right != null)
            stack.add(curNode.right);
    }
    return res;
}
-------------本文结束感谢您的阅读-------------
可以请我喝杯奶茶吗