LeetCode - 590. N叉树的后序遍历 Swift &

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

例如，给定一个 3叉树 :

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

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

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

算法

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 postorder(_ root: Node?) -> [Int] {
        var result = [Int]()
        if root == nil {
            return result
        }
        helper(root!, &result)
        return result
    }
    
    func helper(_ node: Node, _ result: inout [Int]) {
        if !node.children.isEmpty {
            // 递归遍历所有的子节点
            for child in node.children {
                helper(child, &result)
            }
            // 遍历完所有子节点之后，添加这个父节点
            result.append(node.val)
        } else {
            // 没有子节点，直接添加这个节点
            result.append(node.val)
        }
    }

• 迭代

/**
     迭代
     参考题解：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/solution/ncha-shu-de-hou-xu-bian-li-by-leetcode/
     时间复杂度为O(M) M：N叉树的节点个数
     空间复杂度为O(M)
     */
    func postorder(_ root: Node?) -> [Int] {
        var result = [Int]()
        if root == nil {
            return result
        }
        var stack = [Node]()
        stack.append(root!)
        while !stack.isEmpty {
            let current = stack.popLast()
            // 头插
            result.insert(current!.val, at: 0)
            // 子节点存在，依次入栈
            if !current!.children.isEmpty {
                for child in current!.children {
                    stack.append(child)
                }
            }
        }
        return result
    }

Java

• 递归

class Solution {
    List<Integer> list;
    public List<Integer> postorder(Node root) {
        list = new ArrayList<>();
        if (root == null) {
            return list;
        }    
        helper(root);
        return list;
    }

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

• 迭代

/** 迭代 */
    public List<Integer> postorder(Node root) {
        list = new ArrayList<>();
        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) {
                for (Node child : current.children) {
                    stack.push(child);
                }
            }
        }
        Collections.reverse(list);
        return list;
    }

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