LeetCode - 589. N叉树的前序遍历 Swift &

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

例如，给定一个 3叉树 :

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法

Java

• 递归

class Solution {
    List<Integer> list;
    Stack<Node> stack;
    /** 递归 */
    public List<Integer> preorder(Node root) {
        list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        helper(root);
        return list;
    }

    public void helper(Node node) {
        list.add(node.val);
        if (node.children.size() > 0) {
            for (Node child : node.children) {
                helper(child);
            }
        }
    }
}

• 迭代

/** 迭代 */
    public List<Integer> preorder(Node root) {
        List<Integer> list = new ArrayList<>();
        Stack<Node> stack = new Stack<>();  
        if (root == null) {
            return list;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            list.add(current.val);
            if (current.children.size() > 0) {
                Collections.reverse(current.children);
                for (Node child : current.children) {
                    stack.push(child);
                }
            }
        }
        return list;
    }

swift

树结构

// Definition for a Node.
public class Node {
  public var val: Int
  public var children: [Node]
  public init(_ val: Int) {
      self.val = val
      self.children = []
  }
}

• 递归

/**
     递归
     */
    func preorder(_ root: Node?) -> [Int] {
        var result = [Int]()
        if root == nil {
            return result
        }
        helper(root!, &result)
        return result
    }
    
    func helper(_ current: Node, _ result: inout [Int]) {
        result.append(current.val)
        if !current.children.isEmpty {
            for child in current.children {
                helper(child, &result)
            }
        }
    }

• 迭代

/**
     迭代
     */
    func preorder(_ root: Node?) -> [Int] {
        var result = [Int]()
        var stack = [Node]()
        if root == nil {
            return result
        }
        stack.append(root!)
        while !stack.isEmpty {
            let current = stack.popLast()
            result.append(current!.val)
            if !current!.children.isEmpty {
                for child in current!.children.reversed() {
                    stack.append(child)
                }
            }
        }
        return result
    }

GitHub：https://github.com/huxq-coder/LeetCode
欢迎star