Traversing Tree (recursive, iterative)

• Tree traverse 할때 iterative 하게 하려면
• Stack 사용
• level traverse 의 경우 Queue 사용
• Binary Tree 일 경우 node nil 로 loop 가능

N-ary Tree Preorder Traversal - LeetCode

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

class Solution {
    var ans : [Int] = []
    func preorder(_ root: Node?) -> [Int] {
    	//recursive
    	// dfs(root)
        
        //iterative
        guard let root = root else {
            return []
        }
        var stack : [Node] = []
        stack.append(root)
        while !stack.isEmpty {
            let node = stack.removeLast()
            ans.append(node.val)
            for node in node.children.reversed() {
                stack.append(node)
            }
        }
        return ans
    }
    func dfs(_ node : Node?)  {
        guard let node = node else {
            return 
        }
        ans.append(node.val)
        for child in node.children {
            dfs(child)
        }
    }
}