编程知识 cdmana.com

Preorder traversal of n-tree (Java implementation)

Title Description

Given a N Fork tree , Returns the The former sequence traversal .

for example , Given a  3 Fork tree  :

Return its preorder traversal : [1,3,5,6,2,4].

source : Power button (LeetCode) link :https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

Their thinking

recursively , Visit according to The root node —— subtree The way to traverse the tree , When visiting subtrees , A subtree can also be used as n Fork tree , Returns when the node is empty , In this way, you can recurse .

Solution code

Complexity analysis

Time complexity :O(n), among n yes n The number of nodes in the cross tree . Each node is traversed exactly once .

Spatial complexity :O(n), For the stack overhead in recursion , On average O(logn), At worst, the tree is chained , by 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 {
    List<Integer> res = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        helper(root);
        return res;
    }
    public void helper(Node root){
        if(root == null)
            return ;
        res.add(root.val);
        for(int i=0; i<root.children.size(); i++) {
            helper(root.children.get(i));
        }
    }
}

 

版权声明
本文为[Cheng Yu]所创,转载请带上原文链接,感谢

Scroll to Top