树：Java中前序遍历中序遍历后序遍历

81 阅读 0 评论 54 点赞

我是靠谱客的博主俏皮保温杯，这篇文章主要介绍树：Java中前序遍历中序遍历后序遍历，现在分享给大家，希望可以做个参考。

针对树这一数据结构的遍历问题主要有四种，前序遍历、中序遍历、后序遍历、层序遍历，今天我们主要说明一下前序、中序、后序的递归方式代码模板。

前序遍历

前序遍历可以理解为向前遍历，也就是遍历时，时刻保持节点输出顺序为（根-左-右）。

复制代码

1
2
3
4
5
6
7
public List<Integer> qiangxu(TreeNode root, List list) {
    if (root == null) return list;
    list.add(root.val);//根
    qiangxu(root.left,list);//左
    qiangxu(root.right,list);//右
    return list;
}

中序遍历

中序遍历可以理解为向中遍历，也就是遍历时，时刻保持节点输出顺序为（左-根-右），注意二叉搜索树中序遍历一定是递增的

复制代码

1
2
3
4
5
6
7
8
9
//二叉搜索树中中序遍历一定是递增的

public List<Integer> zhongxu(TreeNode root, List list) {
    if (root == null) return list;
    zhongxu(root.left,list);//左
    list.add(root.val);//根
    zhongxu(root.right,list);//右
    return list;
}

后序遍历

后序遍历可以理解为向后遍历，也就是遍历时，时刻保持节点输出顺序为（左-右-根）

复制代码

1
2
3
4
5
6
7
public List<Integer> houxu(TreeNode root, List list) {
    if (root == null) return list;
    houxu(root.left,list);//左
    houxu(root.right,list);//右
    list.add(root.val);//根
    return list;
}

遍历入口

复制代码

1
2
3
4
5
6
public List<Integer> treeInter(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        return zhongxu(root,list);
        return houxu(root,list);
        return qianxu(root,list);
    }