栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

N叉树层序遍历[层次遍历+size分层 || 递归遍历+level分层]

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

N叉树层序遍历[层次遍历+size分层 || 递归遍历+level分层]

N叉树的层次遍历
  • 前言
  • 一、N叉树层次遍历
  • 二、分层遍历
    • 1、递归遍历 + level分层
    • 2、层次遍历+size分层
  • 总结
  • 参考文献

前言

层次遍历是二叉树的基本遍历,分层遍历又是二叉树层次遍历的扩展。二叉遍历和N叉遍历不过是孩子节点由2到N。通过N叉树分层遍历来练习分层的两者思想,层次遍历+size分层 || 递归遍历+level分层。

一、N叉树层次遍历

二、分层遍历 1、递归遍历 + level分层
// N叉树的层序遍历。
public class LevelOrder {
    
    // M1-递归遍历 + level标记
    public List> levelOrder(Node root) {
        // 初始化需要的List来存各层list
        List> rs = new ArrayList<>();
        // 前序遍历 + 分层,使每个节点进入对应的list。
        preOrder(root, rs, 0);
        // 返回分层遍历的节点集。
        return rs;
    }

    // 前序遍历 + level 做到分层取值。
    private void preOrder(Node root, List> rs, int level) {
        // 递归到null节点,终止此次递归。
        if (null == root) return;
        // 获取该root节点所在的list,并把该节点加入。
        List cur = null;
        // 第一次到这么深。
        if (level >= rs.size()) rs.add(cur = new ArrayList<>());
        else cur = rs.get(level);
        // 将该节点放入对应层。
        cur.add(root.val);
        // 递归遍历。
        List next = root.children;
        for (Node node : next) preOrder(node, rs, level + 1);
    }

    // Definition for a Node.
    class Node {
        public int val;
        public List children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List _children) {
            val = _val;
            children = _children;
        }
    }

}
2、层次遍历+size分层
// N叉树的层序遍历。
public class LevelOrder {
    
    // M1-递归遍历 + level标记
    public List> levelOrder(Node root) {
        // 初始化需要的List来存各层list
        List> rs = new ArrayList<>();
        // 前序遍历 + 分层,使每个节点进入对应的list。
        preOrder(root, rs, 0);
        // 返回分层遍历的节点集。
        return rs;
    }

    // 前序遍历 + level 做到分层取值。
    private void preOrder(Node root, List> rs, int level) {
        // 递归到null节点,终止此次递归。
        if (null == root) return;
        // 获取该root节点所在的list,并把该节点加入。
        List cur = null;
        // 第一次到这么深。
        if (level >= rs.size()) rs.add(cur = new ArrayList<>());
        else cur = rs.get(level);
        // 将该节点放入对应层。
        cur.add(root.val);
        // 递归遍历。
        List next = root.children;
        for (Node node : next) preOrder(node, rs, level + 1);
    }

    // Definition for a Node.
    class Node {
        public int val;
        public List children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List _children) {
            val = _val;
            children = _children;
        }
    }

}
总结

1)树分层遍历的两者思想,层次遍历+size分层 || 递归遍历+level分层。

参考文献

[1] LeetCode N叉树层序遍历

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948278.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号