美文网首页
LeetCode题解之N叉树的前序遍历

LeetCode题解之N叉树的前序遍历

作者: l1fe1 | 来源:发表于2020-08-26 08:00 被阅读0次

    N叉树的前序遍历

    题目描述

    给定一个 N 叉树,返回其节点值的前序遍历。

    例如,给定一个 3叉树 :

    示例图

    返回其前序遍历: [1,3,5,6,2,4]。

    **说明: **递归法很简单,你可以使用迭代法完成此题吗?

    解题思路

    使用两个链表来得到 N 叉树的前序遍历结果,其中一个链表作为辅助空间,一个链表用于存放前序遍历的结果。首先把根节点加入辅助链表。然后每次从辅助链表的尾部取出节点,加入到结果链表的头部,每次取出一个节点之后,就把该节点的所有子节点按逆序加入到辅助链表中去(即先添加右边的子节点,再添加左边的子节点)。这样就能确保结果链表中存储的就是 N 叉树的前序遍历结果了。

    复杂度分析

    • 时间复杂度:O(n),其中 n 为树中节点的个数。
    • 空间复杂度:O(n),在最坏的情况下,N 叉树只有两层,这时候需要长度为 n - 1 的辅助空间来存储 N 叉树中的节点,因此空间复杂度为 O(n) 。

    代码实现

    /*
    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> children;
    
        public Node() {}
    
        public Node(int _val) {
            val = _val;
        }
    
        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };
    */
    
    class Solution {
        public List<Integer> preorder(Node root) {
            LinkedList<Node> helper = new LinkedList<>();
            LinkedList<Integer> res = new LinkedList<>();
            if (root == null) {
                return res;
            }
            helper.add(root);
            while (!helper.isEmpty()) {
                Node node = helper.pollLast();
                res.add(node.val);
                Collections.reverse(node.children);
                for (Node n : node.children) {
                    helper.add(n);
                }
            }
            return res;
        }
    }
    

    相关文章

      网友评论

          本文标题:LeetCode题解之N叉树的前序遍历

          本文链接:https://www.haomeiwen.com/subject/olutsktx.html