LeetCode Solutions

			

class Codec {
 public:
  // Encodes an n-ary tree to a binary tree.
  TreeNode* encode(Node* root) {
    if (root == nullptr)
      return nullptr;

    TreeNode* rootTreeNode = new TreeNode(root->val);
    queue<pair<Node*, TreeNode*>> q{{{root, rootTreeNode}}};

    while (!q.empty()) {
      const auto [parentNode, parentTreeNode] = q.front();
      q.pop();
      TreeNode* prevTreeNode = nullptr;
      TreeNode* headTreeNode = nullptr;
      for (Node* child : parentNode->children) {
        TreeNode* currTreeNode = new TreeNode(child->val);
        if (prevTreeNode != nullptr)
          prevTreeNode->right = currTreeNode;
        else
          headTreeNode = currTreeNode;
        prevTreeNode = currTreeNode;
        q.emplace(child, currTreeNode);
      }
      parentTreeNode->left = headTreeNode;
    }

    return rootTreeNode;
  }

  // Decodes your binary tree to an n-ary tree.
  Node* decode(TreeNode* root) {
    if (root == nullptr)
      return nullptr;

    Node* rootNode = new Node(root->val);
    queue<pair<Node*, TreeNode*>> q{{{rootNode, root}}};

    while (!q.empty()) {
      const auto [parentNode, parentTreeNode] = q.front();
      q.pop();
      TreeNode* sibling = parentTreeNode->left;
      while (sibling) {
        Node* currNode = new Node(sibling->val);
        parentNode->children.push_back(currNode);
        q.emplace(currNode, sibling);
        sibling = sibling->right;
      }
    }

    return rootNode;
  }
};

			

class Codec {
  // Encodes an n-ary tree to a binary tree.
  public TreeNode encode(Node root) {
    if (root == null)
      return null;

    TreeNode rootTreeNode = new TreeNode(root.val);
    Queue<Pair<Node, TreeNode>> q = new ArrayDeque<>(Arrays.asList(new Pair<>(root, rootTreeNode)));

    while (!q.isEmpty()) {
      Node parentNode = q.peek().getKey();
      TreeNode parentTreeNode = q.poll().getValue();
      TreeNode prevTreeNode = null;
      TreeNode headTreeNode = null;
      for (Node child : parentNode.children) {
        TreeNode currTreeNode = new TreeNode(child.val);
        if (prevTreeNode == null)
          headTreeNode = currTreeNode;
        else
          prevTreeNode.right = currTreeNode;
        prevTreeNode = currTreeNode;
        q.offer(new Pair<>(child, currTreeNode));
      }
      parentTreeNode.left = headTreeNode;
    }

    return rootTreeNode;
  }

  // Decodes your binary tree to an n-ary tree.
  public Node decode(TreeNode root) {
    if (root == null)
      return null;

    Node rootNode = new Node(root.val, new ArrayList<>());
    Queue<Pair<Node, TreeNode>> q = new ArrayDeque<>(Arrays.asList(new Pair<>(rootNode, root)));

    while (!q.isEmpty()) {
      Node parentNode = q.peek().getKey();
      TreeNode parentTreeNode = q.poll().getValue();
      TreeNode sibling = parentTreeNode.left;
      while (sibling != null) {
        Node currNode = new Node(sibling.val, new ArrayList<>());
        parentNode.children.add(currNode);
        q.offer(new Pair<>(currNode, sibling));
        sibling = sibling.right;
      }
    }

    return rootNode;
  }
}

			

class Codec:
  # Encodes an n-ary tree to a binary tree.
  def encode(self, root: 'Node') -> Optional[TreeNode]:
    if not root:
      return None

    rootTreeNode = TreeNode(root.val)
    q = deque([(root, rootTreeNode)])

    while q:
      parentNode, parentTreeNode = q.popleft()
      prevTreeNode = None
      headTreeNode = None
      for child in parentNode.children:
        currTreeNode = TreeNode(child.val)
        if prevTreeNode:
          prevTreeNode.right = currTreeNode
        else:
          headTreeNode = currTreeNode
        prevTreeNode = currTreeNode
        q.append((child, currTreeNode))
      parentTreeNode.left = headTreeNode

    return rootTreeNode

  # Decodes your binary tree to an n-ary tree.
  def decode(self, root: Optional[TreeNode]) -> 'Node':
    if not root:
      return None

    rootNode = Node(root.val, [])
    q = deque([(rootNode, root)])

    while q:
      parentNode, parentTreeNode = q.popleft()
      sibling = parentTreeNode.left
      while sibling:
        currNode = Node(sibling.val, [])
        parentNode.children.append(currNode)
        q.append((currNode, sibling))
        sibling = sibling.right

    return rootNode