###### tags: `Week_1`, `Tree`

# Tree

## [589. N-ary Tree Preorder Traversal](https://leetcode.com/problems/n-ary-tree-preorder-traversal/)
harry(recursive)

# Definition for a Node.
# class Node
#     attr_accessor :val, :children
#     def initialize(val)
#         @val = val
#         @children = []
#     end
# end

# @param {Node} root
# @return {List[int]}
def preorder(root)
  return [] unless root
  
  if root.children.any?
    [root.val, *root.children.flat_map(&method(:preorder))] 
  else
    [root.val] 
  end
end

harry(iterative)

def preorder(root)
  stack = [root]
  values = []
  while stack.any?
    node = stack.pop
    values << node.val
    stack.concat(node.children.reverse)
  end
  values
end

beny
* Stack: first goin last goout.
* Test: preorder、inorder、postorder

public class Solution {
    public IList<int> Preorder(Node root) {
        List<int> result = new List<int>();
        if(root == null){
            return result;
        }        
        Stack<Node> nodeStack = new Stack<Node>();
        nodeStack.Push(root);
        while(nodeStack.Count > 0){
            Node curr = nodeStack.Pop();
            result.Add(curr.val);  
            foreach(Node node in curr.children.Reverse()){
                if(node != null)
                {
                    nodeStack.Push(node);
                }              
            }      
        }
        return result;        
    }
}

Sam:

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        
        ans = []
        
        def traverse(node):
            if node is None:
                return
            
            ans.append(node.val)
            for child in node.children:
                traverse(child)
        
        traverse(root)
        return ans
        

## [102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

harry

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
  return [] if !root
  return [[root.val]] if root.left.nil? && root.right.nil?
  
  if root.left && root.right
    [[root.val], *merge_array(level_order(root.left), level_order(root.right))]
  elsif root.left
    [[root.val], *level_order(root.left)]
  else # root.right
    [[root.val], *level_order(root.right)]
  end
end


def merge_array(left, right)
  size = left.size > right.size ? left.size : right.size
  0.upto(size-1) do |i|
    break if !right[i]

    if left[i]
      left[i].concat(right[i])
    else
      left[i] = right[i]
    end
  end

  left
end

beny
* Queue: first goin first goout.

public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {        
        List<IList<int>> result = new List<IList<int>>();        
        if(root == null){
            return result;
        }
        IList<int> list = null;   
        Queue<TreeNode> nodequeue = new Queue<TreeNode>();
        nodequeue.Enqueue(root);
        while(nodequeue.Count > 0){
            list = new List<int>(); 
            int levelNum = nodequeue.Count;
            for(int i = 0; i < levelNum; i++){  
                if(nodequeue.Peek().left != null){
                    nodequeue.Enqueue(nodequeue.Peek().left);
                }    
                if(nodequeue.Peek().right != null){
                    nodequeue.Enqueue(nodequeue.Peek().right);
                }
                list.Add(nodequeue.Dequeue().val);                
            }    
            result.Add(list);              
        }
        return result;        
    }
}

Sam:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import queue
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        if root is None:
            return []
        my_q = queue.Queue()
        my_q.put(root)
        levels = 0
        while not my_q.empty():
            ans.append([])
            level_count = my_q.qsize()  
            for _ in range(level_count):
                rt = my_q.get()
                ans[levels].append(rt.val)
                if rt.left:
                    my_q.put(rt.left)
                if rt.right:
                    my_q.put(rt.right)
            levels += 1   
        return ans