樹的序列化與字串編解碼

Serialize each subtree as a unique string: "val,left,right"
  → null nodes become "#" (marker) to preserve tree structure
  → Store in Map<String, Integer> to count occurrences
  → If count reaches 2, it's a duplicate → add to result

Tree:        1
            / \
           2   2
          /     \
         4       4

Pre-order serialization (WRONG — builds string top-down):
  node 2 (left)  → "2,4,#"   ← built before knowing full subtree
  node 2 (right) → "2,#,4"   ← different string, but structurally different → OK here

Post-order serialization (CORRECT — builds string bottom-up):
  node 4 (left)  → "4,#,#"
  node 4 (right) → "4,#,#"   ← same! correctly identified as duplicate
  node 2 (left)  → "2,4,#,#,#"
  node 2 (right) → "2,#,4,#,#"  ← different (4 is left child vs right child)

Key insight: only post-order guarantees the full subtree structure is
captured before building the parent's key.

// Template: Post-order DFS + Subtree Serialization (LC 652)
Map<String, Integer> pathMap = new HashMap<>();  // { serialized_string : count }
List<TreeNode> result = new ArrayList<>();

List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    serialize(root);
    return result;
}

private String serialize(TreeNode node) {
    if (node == null) {
        return "#";  // null marker — preserves tree structure
    }

    // 1. Post-order: recurse into children FIRST
    String left  = serialize(node.left);
    String right = serialize(node.right);

    // 2. Build current subtree's unique identity
    //    Use delimiter to prevent "1,11" vs "11,1" ambiguity
    String key = node.val + "," + left + "," + right;

    // 3. Count occurrences
    int count = pathMap.getOrDefault(key, 0);

    // 4. Add to result ONLY when count == 1 (second occurrence = first duplicate)
    //    count == 1 means: this subtree appeared before, so current is a duplicate
    if (count == 1) {
        result.add(node);
    }

    // 5. Update count regardless
    pathMap.put(key, count + 1);

    // 6. Return serialization so parent can use it
    return key;
}

Tree:       1
           / \
          2   3
         /
        4

Serialization (post-order):
  node 4 → "4,#,#"
  node 2 → "2,4,#,#,#"    (val=2, left="4,#,#", right="#")
  node 3 → "3,#,#"
  node 1 → "1,2,4,#,#,#,3,#,#"

count == 0  → first time seen, just record
count == 1  → seen exactly once before → current is a DUPLICATE → add to result
count >= 2  → already recorded, skip (avoid adding same duplicate multiple times)

// All of these produce unambiguous serializations:
node.val + "," + left + "," + right   // V0, V1 in FindDuplicateSubtrees.java (recommended)
node.val + "$" + left + "$" + right   // V2 (alternative)
node.val + " "  + left + " "  + right // V3 (using space)
node.val + "#"  + left + "#"  + right // V4 (using # as delimiter)
// Avoid concatenating without delimiter: "112" is ambiguous (1+12 vs 11+2)

// Approach 1: Add when count == 1 (this subtree appeared before)
int count = pathMap.getOrDefault(key, 0);
if (count == 1) {
    result.add(node);  // 2nd occurrence → first duplicate
}
pathMap.put(key, count + 1);

// Approach 2: Add when count == 2 (we just found second occurrence)
pathMap.put(key, pathMap.getOrDefault(key, 0) + 1);
if (pathMap.get(key) == 2) {
    result.add(node);  // Just became a duplicate
}

// Style 1: Instance variables (mutable state in class)
class Solution {
    Map<String, Integer> pathMap = new HashMap<>();
    List<TreeNode> result = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        serialize(root);
        return result;
    }

    private String serialize(TreeNode node) {
        // ... implementation ...
    }
}

// Style 2: Local variables + pass through parameters
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    Map<String, Integer> pathMap = new HashMap<>();
    List<TreeNode> result = new ArrayList<>();
    serialize(root, pathMap, result);
    return result;
}

private String serialize(TreeNode node, Map<String, Integer> pathMap, List<TreeNode> result) {
    // ... implementation ...
}

Goal: build a unique "fingerprint" string for each subtree.

Pre-order (root → left → right):
  → builds the key at the ROOT first, before children are known
  → can't include children's serialized forms at build time
  → would require a separate recursive pass → O(N²) and messy

Post-order (left → right → root):
  → left child already returned its serialized string
  → right child already returned its serialized string
  → current key = val + "," + leftKey + "," + rightKey   ← O(1) to build
  → naturally bubbles the full subtree fingerprint up to the parent
  → one DFS pass is enough: O(N) time

Rule: if you need the COMPLETE subtree structure in the key, use post-order.

# python
# LC 652 Find Duplicate Subtrees
from collections import defaultdict

def findDuplicateSubtrees(root):
    """
    IDEA: Node Path Pattern

    Time: O(N²) worst case (string operations), O(N) with optimization
    Space: O(N) for HashMap and recursion
    """
    result = []
    path_count = defaultdict(int)

    def get_node_path(node):
        if not node:
            return "#"

        # Post-order: left → right → node
        left = get_node_path(node.left)
        right = get_node_path(node.right)

        # Build serialization string
        path = f"{node.val},{left},{right}"

        # Track frequency
        if path_count[path] == 1:
            result.append(node)
        path_count[path] += 1

        return path

    get_node_path(root)
    return result

// java
// LC 572 Subtree of Another Tree
/**
 * IDEA: Node Path Pattern for Subtree Matching
 *
 * Approach 1: Serialize both trees and check if subRoot is substring of root
 * Approach 2: Traditional recursive comparison (shown below)
 */

// Method 1: Using Node Path Serialization
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    String rootPath = serialize(root);
    String subPath = serialize(subRoot);

    // NOTE !!! serialize() already wraps every node in commas, so subPath arrives
    //          delimited on both sides. Adding another pair searches for ",,...,,"
    //          and returns false even for root = [1], subRoot = [1].
    return rootPath.contains(subPath);
}

private String serialize(TreeNode node) {
    if (node == null) {
        return "#";
    }

    // Post-order serialization with delimiters
    String left = serialize(node.left);
    String right = serialize(node.right);

    // Add delimiters to prevent false matches (e.g., "12" in "123")
    return "," + node.val + "," + left + "," + right + ",";
}

// Method 2: Traditional Recursive Comparison
public boolean isSubtree_v2(TreeNode root, TreeNode subRoot) {
    if (root == null) {
        return false;
    }

    // Check if current tree matches OR check subtrees
    return isSameTree(root, subRoot) ||
           isSubtree_v2(root.left, subRoot) ||
           isSubtree_v2(root.right, subRoot);
}

private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    if (p.val != q.val) return false;

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

# python
# LC 572 Subtree of Another Tree

# Method 1: Node Path Serialization
def isSubtree(root, subRoot):
    """
    Serialize both trees and check substring match

    Time: O(M + N) where M, N are tree sizes
    Space: O(M + N) for serialization strings
    """
    def serialize(node):
        if not node:
            return "#"

        # Post-order with delimiters
        left = serialize(node.left)
        right = serialize(node.right)

        return f",{node.val},{left},{right},"

    root_path = serialize(root)
    sub_path = serialize(subRoot)

    return sub_path in root_path

# Method 2: Traditional Recursive
def isSubtree_v2(root, subRoot):
    if not root:
        return False

    def is_same(p, q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        return (p.val == q.val and
                is_same(p.left, q.left) and
                is_same(p.right, q.right))

    return (is_same(root, subRoot) or
            isSubtree_v2(root.left, subRoot) or
            isSubtree_v2(root.right, subRoot))

      encode                                    decode
   ┌──────────┐                              ┌──────────┐
   │  tree    │ ── "{}({})({})".format() ──► │  string  │
   │          │ ◄── parse val, then '(' ──── │          │
   └──────────┘                              └──────────┘
   returns str going UP                      returns (node, idx) going UP

# python — every tree→string problem is this, with a different FMT + NULL
def encode(node):
    if not node:
        return NULL          # "" for parens, "#" for comma-format
    return FMT.format(node.val, encode(node.left), encode(node.right))

 Case                      Full form        Emitted        Why
 ─────────────────────────────────────────────────────────────────────────────────
 leaf                      1()()            1              both pairs useless
 left only                 1(2)()           1(2)           trailing () carries no info
 right only  ⚠️            1()(3)           1()(3)         MUST keep the left placeholder!
 both                      1(2)(3)          1(2)(3)        nothing to drop

# python
# LC 606 - Construct String from Binary Tree  (2-rule form — preferred)
# IDEA: pre-order DFS returning a string; left pair kept if ANY child exists
# time = O(N) with a list/StringBuilder (O(N^2) with naive `+` on strings), space = O(H)
class Solution:
    def tree2str(self, root):
        if not root:
            return ""
        s = str(root.val)
        if root.left or root.right:          # left placeholder needed if ANY child
            s += "(" + self.tree2str(root.left) + ")"
        if root.right:                       # right only when it exists
            s += "(" + self.tree2str(root.right) + ")"
        return s

# python
# LC 606 - same thing, written as the explicit `format` template (matches the FMT table above)
# time = O(N), space = O(H)
class Solution:
    def tree2str(self, root):
        if not root:
            return ""
        # Case 1: leaf -> bare value
        if not root.left and not root.right:
            return str(root.val)
        # Case 2: no right child -> omit the trailing ()
        if not root.right:
            return "{}({})".format(root.val, self.tree2str(root.left))
        # Case 3: right child exists -> left may render as the empty "()" placeholder
        return "{}({})({})".format(
            root.val,
            self.tree2str(root.left),
            self.tree2str(root.right)
        )

// java
// LC 606 - Construct String from Binary Tree
// IDEA: pre-order DFS + StringBuilder (avoid O(N^2) string concat)
// time = O(N), space = O(H)
public String tree2str(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    dfs(root, sb);
    return sb.toString();
}

private void dfs(TreeNode node, StringBuilder sb) {
    if (node == null) return;
    sb.append(node.val);
    if (node.left != null || node.right != null) {   // left placeholder rule
        sb.append('(');
        dfs(node.left, sb);
        sb.append(')');
    }
    if (node.right != null) {
        sb.append('(');
        dfs(node.right, sb);
        sb.append(')');
    }
}

        1              tree2str(4) = "4"                      (leaf)
       / \             tree2str(2) = "2" + "(4)"     = "2(4)"  (left only)
      2   3            tree2str(3) = "3"                      (leaf)
     /                 tree2str(1) = "1" + "(2(4))" + "(3)"
    4                              = "1(2(4))(3)"

        1              tree2str(4) = "4"
       / \             tree2str(2) = "2" + "()" + "(4)" = "2()(4)"   ← left pair KEPT
      2   3                          ^^^^ empty, but required
       \
        4              tree2str(1) = "1(2()(4))(3)"

# python
# LC 536 - Construct Binary Tree from String   (input: "4(2(3)(1))(6(5))")
# IDEA: recursive descent parser; helper returns (node, next_index)
# time = O(N)  each char consumed once
# space = O(H) recursion depth
class Solution(object):
    def str2tree(self, s):
        if not s:
            return None
        root, _ = self.helper(s, 0)
        return root

    def helper(self, s, idx):
        n = len(s)

        # 1) parse the value: optional '-' then digits (multi-digit!)
        sign = 1
        if s[idx] == '-':
            sign = -1
            idx += 1
        num = 0
        while idx < n and s[idx].isdigit():
            num = num * 10 + int(s[idx])
            idx += 1

        node = TreeNode(sign * num)

        # 2) first '(' -> LEFT subtree
        if idx < n and s[idx] == '(':
            node.left, idx = self.helper(s, idx + 1)   # +1 skips '('
            idx += 1                                   # skip the matching ')'

        # 3) second '(' -> RIGHT subtree
        if idx < n and s[idx] == '(':
            node.right, idx = self.helper(s, idx + 1)
            idx += 1

        return node, idx

// java
// LC 536 - Construct Binary Tree from String
// IDEA: recursive descent; int[] idx acts as a by-reference cursor
// time = O(N), space = O(H)
public TreeNode str2tree(String s) {
    if (s == null || s.isEmpty()) return null;
    return helper(s, new int[]{0});
}

private TreeNode helper(String s, int[] idx) {
    // 1) value (handles '-' and multi-digit)
    int sign = 1;
    if (s.charAt(idx[0]) == '-') { sign = -1; idx[0]++; }
    int num = 0;
    while (idx[0] < s.length() && Character.isDigit(s.charAt(idx[0]))) {
        num = num * 10 + (s.charAt(idx[0]) - '0');
        idx[0]++;
    }
    TreeNode node = new TreeNode(sign * num);

    // 2) left
    if (idx[0] < s.length() && s.charAt(idx[0]) == '(') {
        idx[0]++;                       // skip '('
        node.left = helper(s, idx);
        idx[0]++;                       // skip ')'
    }
    // 3) right
    if (idx[0] < s.length() && s.charAt(idx[0]) == '(') {
        idx[0]++;
        node.right = helper(s, idx);
        idx[0]++;
    }
    return node;
}

# python
# LC 536 - split on the '(' that closes at balance == 0
# time = O(N^2) (string slicing), space = O(N)
class Solution(object):
    def str2tree(self, s):
        if not s:
            return None

        first = s.find('(')
        if first == -1:                       # no children -> pure value
            return TreeNode(int(s))

        root = TreeNode(int(s[:first]))       # int() handles the '-' for us

        # find the ')' matching the FIRST '(' via parenthesis balance
        bal, left_end = 0, -1
        for i in range(first, len(s)):
            if s[i] == '(':
                bal += 1
            elif s[i] == ')':
                bal -= 1
            if bal == 0:
                left_end = i
                break

        root.left = self.str2tree(s[first + 1: left_end])   # inside 1st pair
        if left_end + 1 < len(s):
            root.right = self.str2tree(s[left_end + 2: -1]) # inside 2nd pair
        return root

# python
# LC 297 - Serialize and Deserialize Binary Tree
# IDEA: pre-order with "#" for null; decode consumes the token stream via iter()
# time = O(N) both ways, space = O(N)
class Codec:
    def serialize(self, root):
        def dfs(node):
            if not node:
                return "#"
            # SAME shape as LC 606 -- only FMT and NULL changed
            return "{},{},{}".format(node.val, dfs(node.left), dfs(node.right))
        return dfs(root)

    def deserialize(self, data):
        it = iter(data.split(","))          # the cursor, for free
        def dfs():
            v = next(it)
            if v == "#":
                return None
            node = TreeNode(int(v))
            node.left = dfs()               # pre-order: left BEFORE right
            node.right = dfs()
            return node
        return dfs()

# python
# LC 1028 - Recover a Tree From Preorder Traversal   ("1-2--3--4-5--6--7")
# IDEA: dashes = depth; stack holds the current root-to-node path
# time = O(N), space = O(H)
class Solution:
    def recoverFromPreorder(self, traversal):
        stack, i, n = [], 0, len(traversal)
        while i < n:
            depth = 0
            while traversal[i] == '-':      # 1) count dashes -> depth
                depth += 1
                i += 1
            j = i
            while j < n and traversal[j] != '-':
                j += 1
            node = TreeNode(int(traversal[i:j]))
            i = j

            while len(stack) > depth:       # 2) pop back up to this node's parent
                stack.pop()
            if stack:
                parent = stack[-1]
                if not parent.left:         # 3) pre-order -> left fills first
                    parent.left = node
                else:
                    parent.right = node
            stack.append(node)
        return stack[0] if stack else None

// java
// algorithm book (labu) p.256

String SEP = ",";
String NULL = "#";

/* main func : serialize binary tree to string */
String serialize(TreeNode root){
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
}

/* help func : put binary tree to StringBuilder */
void serialize(TreeNode root, StringBuilder sb){
    if (root == null){
        sb.append(NULL).append(SEP);
        return;
    }

    /********* pre-order traverse *********/
    sb.append(root.val).append(SEP);
    /**************************************/

    serialize(root.left, sb);
    serialize(root.right, sb);
}

// java
// algorithm book (labu) p.256

String SEP = ",";
String NULL = "#";

/* main func : dserialize string to binary tree */
TreeNode deserlialize(String data){
    // transform string to linkedlist
    LinkedList<String> nodes = new LinkedList<>();
    for (String s: data.split(SEP)){
        nodes.addLast(s);
    }
    return deserlialize(nodes);
}


/* **** help func : build binary tree via linkedlist (nodes) */
TreeNode deserlialize(LinkedList<String> nodes){
    if (nodes.isEmpty()) return null;

    /********* pre-order traverse *********/
    // the 1st element on left is the root node of the binary tree
    String first = nodes.removeFirst();
    if (first.equals(NULL)) return null;
    TreeNode root = new TreeNode(Integer.parseInt(first));
    /**************************************/

    root.left = deserlialize(nodes);
    root.right = deserlialize(nodes);

    return root;
}

// java
// algorithm book (labu) p.258

String SEP = ",";
String NULL = "#";

StringBuilder sb = new StringBuilder();

/* help func : pit binary tree to StringBuilder*/
void serialize(TreeNode root, StringBuilder sb){
    if (root == null){
        sb.append(NULL).append(SEP);
        return;
    }

    serialize(root.left, sb);
    serialize(root.right, sb);

    /********* post-order traverse *********/
    sb.append(root.val).append(SEP);
    /**************************************/
}

// java
// algorithm book (labu) p.260

/* main func : deserialize string to binary tree */
TreeNode deserlialize(String data){
    LinkedList<String> nodes = new LinkedList<>();
    for (String s : data.split(SEP)){
        nodes.addLast(s);
    }
    return deserlialize(nodes);
}

/* help func : build binary tree via linkedlist */
TreeNode deserlialize(LinkedList<String> nodes){
    if (nodes.isEmpty()) return null;
    // get element from last to beginning
    String last = nodes.removeLast();

    if (last.equals(NULL)) return null;
    TreeNode root = new TreeNode(Integer.parseInt(last));
    // build right sub tree first, then left sub tree
    root.right = deserlialize(nodes);
    root.left = deserlialize(nodes);

    return root;
}

// java
// layer traverse : tree.html#1-1-basic-op
// algorithm book (labu) p.263
String SEP = ",";
String NULL = "#";

/* Serialize binary tree to string */
String serialize(TreeNode root){

    if (root == null) return "";
    StringBuilder sb = new StringBuilder();

    // init queue, put root into it
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()){
        TreeNode cur = q.poll();

        /***** layer traverse ******/
        if (cur == null){
            sb.append(NULL).append(SEP);
            continue;
        }
        sb.append(cur.val).append(SEP);
        /**************************/

        q.offer(cur.left);
        q.offer(cur.right);
    }
    return sb.toString();
}

// java
// algorithm book (labu) p.264

String SEP = ",";
String NULL = "#";

/* Deserialize binary tree to string */
TreeNode deserlialize(String data){
    
    if (data.isEmpty()) return null;

    String[] nodes = data.split(SEP);

    // root's value = 1st element's value
    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));

    // queue records parent node, put root into queue
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    for (int i = 1; i < nodes.length){

        // queue saves parent nodes
        TreeNode parent = q.poll();
        
        // parent node's left sub node
        String left = nodes[i++];
        if (!left.equals(NULL)){
            parent.left = new TreeNode(Integer.parseInt(left));
            q.offer(parent.left);
        }else {
            parent.left = null;
        }
        // parent node's right sub node
        String right = nodes[i++];
        if (!right.equals(NULL)){
            parent.right = new TreeNode(Integer.parseInt(right));
            q.offer(parent.right);
        }else{
            parent.right = null;
        }
    }

    return root;
}

// java
// LC 297
public class Codec{
    public String serialize(TreeNode root) {

        /** NOTE !!!
         *
         *     if root == null, return "#"
         */
        if (root == null){
            return "#";
        }

        /** NOTE !!! return result via pre-order, split with "," */
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    public TreeNode deserialize(String data) {

        /** NOTE !!!
         *
         *   1) init queue and append serialize output
         *   2) even use queue, but helper func still using DFS
         */
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
        return helper(queue);
    }

    private TreeNode helper(Queue<String> queue) {

        // get val from queue first
        String s = queue.poll();

        if (s.equals("#")){
            return null;
        }
        /** NOTE !!! init current node  */
        TreeNode root = new TreeNode(Integer.valueOf(s));
        /** NOTE !!!
         *
         *    since serialize is "pre-order",
         *    deserialize we use "pre-order" as well
         *    e.g. root -> left sub tree -> right sub tree
         *    -> so we get sub tree via below :
         *
         *       root.left = helper(queue);
         *       root.right = helper(queue);
         *
         */
        root.left = helper(queue);
        root.right = helper(queue);
        /** NOTE !!! don't forget to return final deserialize result  */
        return root;
    }
}