Same Tree

This approach involves converting each tree into a unique string representation (a process called serialization). If the resulting strings for both trees are identical, the trees are considered the same. A pre-order traversal is a good candidate for serialization, ensuring that null children are also represented to capture the tree's structure accurately.

• Define a helper function serialize(node, stringBuilder) that performs a pre-order traversal.
• In the helper function, if the current node is null, append a special marker (e.g., "#") and a delimiter to the string builder.
• If the node is not null, append its value and a delimiter, then recursively call serialize for the left and right children.
• Create two StringBuilder instances.
• Call the serialize function for the root of tree p and tree q to generate their string representations.
• Compare the two resulting strings. If they are equal, the trees are identical.

The core idea is to transform the 2D tree structure into a 1D string format. We can define a recursive function that performs a pre-order traversal on a tree. When it encounters a node, it appends the node's value to a string. When it encounters a null child, it appends a special marker (like '#') to signify the absence of a node. This is crucial to distinguish between trees like [1,2] and [1,null,2]. After generating the serialized strings for both trees p and q, we simply compare them. If the strings are equal, the trees are structurally and valuably identical.

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        StringBuilder sb1 = new StringBuilder();
        serialize(p, sb1);
        String s1 = sb1.toString();

        StringBuilder sb2 = new StringBuilder();
        serialize(q, sb2);
        String s2 = sb2.toString();

        return s1.equals(s2);
    }

    private void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val).append(",");
        serialize(node.left, sb);
        serialize(node.right, sb);
    }
}