leetcode讲解--589. N-ary Tree Preorder Traversal_Node.js

上一篇: 树莓派 - 远程调试nodejs 下一篇:node-coap入门（二）——json

leetcode讲解--589. N-ary Tree Preorder Traversal

发布时间：2019-06-29 发布网站：脚本宝典

脚本宝典收集整理的这篇文章主要介绍了leetcode讲解--589. N-ary Tree Preorder Traversal，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目
Given an n-ary tree, return the preorder traversal of its nodes' values.
For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].
Note:
Recursive solution is trivial, could you do it iteratively?
题目地址
讲解
如果用递归来解题的话，还是非常简单的。如果要用迭代来解题，无非就是用栈来实现。要注意的一点是，需要一个额外的栈来把压栈的顺序倒一下序。
Java代码
递归代码：

      
      
      ArrayList<>();
    public List preorder(Node root) {
        if(root==null){
            return result;
        }
        result.add(root.val);
        for(Node node:root.children){
            preorder(node);
        }
        return result;
    }
}" title="" data-original-title="复制">
      
      
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if(root==null){
            return result;
        }
        result.add(root.val);
        for(Node node:root.children){
            preorder(node);
        }
        return result;
    }
}
迭代代码：

      
      
      ArrayList<>();
    private Stack stack = new Stack<>();
    private Stack stack_temp = new Stack();
    public List preorder(Node root) {
        if(root==null){
            return result;
        }
        stack.push(root);
        while(!stack.empty()){
            Node theNode = stack.pop();
            result.add(theNode.val);
            for(Node node:theNode.children){
                stack_temp.push(node);
            }
            while(!stack_temp.empty()){
                stack.push(stack_temp.pop());
            }
        }
        return result;
    }
}" title="" data-original-title="复制">
      
      
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new ArrayList<>();
    private Stack<Node> stack = new Stack<>();
    private Stack<Node> stack_temp = new Stack();
    public List<Integer> preorder(Node root) {
        if(root==null){
            return result;
        }
        stack.push(root);
        while(!stack.empty()){
            Node theNode = stack.pop();
            result.add(theNode.val);
            for(Node node:theNode.children){
                stack_temp.push(node);
            }
            while(!stack_temp.empty()){
                stack.push(stack_temp.pop());
            }
        }
        return result;
    }
}