前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二叉树的5种遍历方式

二叉树的5种遍历方式

作者头像
伊泽瑞尔
发布2022-06-01 08:42:48
1.2K0
发布2022-06-01 08:42:48
举报
文章被收录于专栏:大数据与知识图谱

一、遍历方式

前序遍历:根 左 右

中序遍历:左 根 右

后序遍历:左 右 根

层序遍历:从根开始一层层从左到右遍历

锯齿形层序遍历:层序遍历的变种,要求我们按层数的奇偶来决定每一层的输出顺序。规定二叉树的根节点为第 0 层,如果当前层数是偶数,从左至右输出当前层的节点值,否则,从右至左输出当前层的节点值。

二、代码

1.前序遍历:根 左 右

代码语言:javascript
复制
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

2.中序遍历:左 根 右

代码语言:javascript
复制
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

3.后序遍历:左 右 根

代码语言:javascript
复制
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

4.层序遍历:从根开始一层层从左到右遍历

代码语言:javascript
复制
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        return ret;
    }
}

5.锯齿形层序遍历:层序遍历的变种,要求我们按层数的奇偶来决定每一层的输出顺序。规定二叉树的根节点为第 0 层,如果当前层数是偶数,从左至右输出当前层的节点值,否则,从右至左输出当前层的节点值。

代码语言:javascript
复制
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;
        while (!nodeQueue.isEmpty()) {
            // 双端队列是一个可以在队列任意一端插入元素的队列。变量isOrderLeft记录从左至右,还是从右至左
            // 如果从左至右,我们每次将被遍历到的元素插入至双端队列的末尾。
            // 如果从右至左,我们每次将被遍历到的元素插入至双端队列的头部。
            Deque<Integer> levelList = new LinkedList<Integer>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);
                } else {
                    levelList.offerFirst(curNode.val);
                }
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;
        }
        return ans;
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-03-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 大数据与知识图谱 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档