// Perfect subtrees counted by formula; recurse only the ragged path.
int leftH(TreeNode* n)  { int h = 0; while (n) { h++; n = n->left;  } return h; }
int rightH(TreeNode* n) { int h = 0; while (n) { h++; n = n->right; } return h; }
int countNodes(TreeNode* root) {
    if (!root) return 0;
    int lh = leftH(root), rh = rightH(root);
    if (lh == rh) return (1 << lh) - 1;      // perfect: 2^lh - 1
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Perfect subtrees counted by formula; recurse only the ragged path.
int leftH(TreeNode n)  { int h = 0; while (n != null) { h++; n = n.left;  } return h; }
int rightH(TreeNode n) { int h = 0; while (n != null) { h++; n = n.right; } return h; }
public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int lh = leftH(root), rh = rightH(root);
    if (lh == rh) return (1 << lh) - 1;      // perfect: 2^lh - 1
    return 1 + countNodes(root.left) + countNodes(root.right);
}

# Perfect subtrees counted by formula; recurse only the ragged path.
def countNodes(root):
    def leftH(n):
        h = 0
        while n: h, n = h + 1, n.left
        return h
    def rightH(n):
        h = 0
        while n: h, n = h + 1, n.right
        return h
    if not root:
        return 0
    lh, rh = leftH(root), rightH(root)
    if lh == rh:
        return (1 << lh) - 1                 # perfect: 2^lh - 1
    return 1 + countNodes(root.left) + countNodes(root.right)

// Preorder gives roots; inorder (via a map) splits each subtree.
unordered_map<int,int> pos; int preIdx = 0;
TreeNode* build(vector<int>& pre, int inL, int inR) {
    if (inL > inR) return nullptr;
    int rootVal = pre[preIdx++];             // next root, preorder front-to-back
    TreeNode* root = new TreeNode(rootVal);
    int mid = pos[rootVal];                   // its split point in inorder
    root->left  = build(pre, inL, mid - 1);
    root->right = build(pre, mid + 1, inR);
    return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    for (int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i;
    preIdx = 0;
    return build(preorder, 0, inorder.size() - 1);
}

// Preorder gives roots; inorder (via a map) splits each subtree.
Map<Integer,Integer> pos = new HashMap<>();
int preIdx = 0;
TreeNode build(int[] pre, int inL, int inR) {
    if (inL > inR) return null;
    int rootVal = pre[preIdx++];              // next root, preorder front-to-back
    TreeNode root = new TreeNode(rootVal);
    int mid = pos.get(rootVal);               // its split point in inorder
    root.left  = build(pre, inL, mid - 1);
    root.right = build(pre, mid + 1, inR);
    return root;
}
public TreeNode buildTree(int[] pre, int[] in) {
    for (int i = 0; i < in.length; i++) pos.put(in[i], i);
    return build(pre, 0, in.length - 1);
}

# Preorder gives roots; inorder (via a map) splits each subtree.
def buildTree(preorder, inorder):
    pos = {v: i for i, v in enumerate(inorder)}
    preIdx = 0
    def build(inL, inR):
        nonlocal preIdx
        if inL > inR:
            return None
        rootVal = preorder[preIdx]; preIdx += 1   # next root, front-to-back
        root = TreeNode(rootVal)
        mid = pos[rootVal]                          # split point in inorder
        root.left  = build(inL, mid - 1)
        root.right = build(mid + 1, inR)
        return root
    return build(0, len(inorder) - 1)

// Postorder (from the back) gives roots; build RIGHT before left.
unordered_map<int,int> pos; int postIdx;
TreeNode* build(vector<int>& post, int inL, int inR) {
    if (inL > inR) return nullptr;
    int rootVal = post[postIdx--];           // roots come out root-right-left
    TreeNode* root = new TreeNode(rootVal);
    int mid = pos[rootVal];
    root->right = build(post, mid + 1, inR); // RIGHT first
    root->left  = build(post, inL, mid - 1);
    return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    for (int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i;
    postIdx = postorder.size() - 1;
    return build(postorder, 0, inorder.size() - 1);
}

// Postorder (from the back) gives roots; build RIGHT before left.
Map<Integer,Integer> pos = new HashMap<>();
int postIdx;
TreeNode build(int[] post, int inL, int inR) {
    if (inL > inR) return null;
    int rootVal = post[postIdx--];            // roots come out root-right-left
    TreeNode root = new TreeNode(rootVal);
    int mid = pos.get(rootVal);
    root.right = build(post, mid + 1, inR);   // RIGHT first
    root.left  = build(post, inL, mid - 1);
    return root;
}
public TreeNode buildTree(int[] in, int[] post) {
    for (int i = 0; i < in.length; i++) pos.put(in[i], i);
    postIdx = post.length - 1;
    return build(post, 0, in.length - 1);
}

# Postorder (from the back) gives roots; build RIGHT before left.
def buildTree(inorder, postorder):
    pos = {v: i for i, v in enumerate(inorder)}
    postIdx = len(postorder) - 1
    def build(inL, inR):
        nonlocal postIdx
        if inL > inR:
            return None
        rootVal = postorder[postIdx]; postIdx -= 1   # root-right-left order
        root = TreeNode(rootVal)
        mid = pos[rootVal]
        root.right = build(mid + 1, inR)             # RIGHT first
        root.left  = build(inL, mid - 1)
        return root
    return build(0, len(inorder) - 1)

// Preorder with '#' null markers; deserialize consumes tokens in order.
string serialize(TreeNode* root) {
    string s;
    function<void(TreeNode*)> dfs = [&](TreeNode* n) {
        if (!n) { s += "#,"; return; }
        s += to_string(n->val) + ",";
        dfs(n->left); dfs(n->right);
    };
    dfs(root);
    return s;
}
TreeNode* deserialize(string data) {
    int i = 0;
    function<TreeNode*()> build = [&]() -> TreeNode* {
        int j = data.find(',', i);
        string tok = data.substr(i, j - i); i = j + 1;
        if (tok == "#") return nullptr;
        TreeNode* n = new TreeNode(stoi(tok));
        n->left = build(); n->right = build();
        return n;
    };
    return build();
}

// Preorder with '#' null markers; deserialize consumes tokens in order.
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    dfs(root, sb);
    return sb.toString();
}
private void dfs(TreeNode n, StringBuilder sb) {
    if (n == null) { sb.append("#,"); return; }
    sb.append(n.val).append(',');
    dfs(n.left, sb); dfs(n.right, sb);
}
private int idx;
public TreeNode deserialize(String data) {
    idx = 0;
    return build(data.split(","));
}
private TreeNode build(String[] t) {
    String tok = t[idx++];
    if (tok.equals("#")) return null;         // marker ends this branch
    TreeNode node = new TreeNode(Integer.parseInt(tok));
    node.left  = build(t);                    // stream order encodes the shape
    node.right = build(t);
    return node;
}

# Preorder with '#' null markers; deserialize consumes tokens in order.
class Codec:
    def serialize(self, root):
        out = []
        def dfs(n):
            if not n:
                out.append('#'); return
            out.append(str(n.val))
            dfs(n.left); dfs(n.right)
        dfs(root)
        return ','.join(out)

    def deserialize(self, data):
        it = iter(data.split(','))
        def build():
            tok = next(it)
            if tok == '#':
                return None
            n = TreeNode(int(tok))
            n.left = build(); n.right = build()
            return n
        return build()

// In-place: splice the right subtree onto the left subtree's tail.
void flatten(TreeNode* root) {
    TreeNode* cur = root;
    while (cur) {
        if (cur->left) {
            TreeNode* prev = cur->left;
            while (prev->right) prev = prev->right;   // rightmost of left subtree
            prev->right = cur->right;                 // old right hangs off it
            cur->right = cur->left;                   // left subtree becomes right
            cur->left = nullptr;
        }
        cur = cur->right;                             // advance down the list
    }
}

// In-place: splice the right subtree onto the left subtree's tail.
public void flatten(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left != null) {
            TreeNode prev = cur.left;
            while (prev.right != null) prev = prev.right;  // rightmost of left
            prev.right = cur.right;            // old right hangs off it
            cur.right = cur.left;              // left subtree becomes right
            cur.left = null;
        }
        cur = cur.right;                       // walk the growing list
    }
}

# In-place: splice the right subtree onto the left subtree's tail.
def flatten(root):
    cur = root
    while cur:
        if cur.left:
            prev = cur.left
            while prev.right:                          # rightmost of left subtree
                prev = prev.right
            prev.right = cur.right                     # old right hangs off it
            cur.right = cur.left                       # left subtree becomes right
            cur.left = None
        cur = cur.right                                # advance down the list

// Return (rob, notRob); collapse to max only at the root.
pair<int,int> solve(TreeNode* node) {
    if (!node) return {0, 0};
    auto [lr, ln] = solve(node->left);
    auto [rr, rn] = solve(node->right);
    int rob    = node->val + ln + rn;         // rob node -> skip children
    int notRob = max(lr, ln) + max(rr, rn);   // skip node -> children free
    return {rob, notRob};
}
int rob(TreeNode* root) {
    auto [r, nr] = solve(root);
    return max(r, nr);
}

// Return (rob, notRob) as a 2-slot array; collapse to max only at the root.
int[] solve(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] l = solve(node.left);
    int[] r = solve(node.right);
    int rob    = node.val + l[1] + r[1];                  // rob -> skip children
    int notRob = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);  // children free
    return new int[]{rob, notRob};
}
public int rob(TreeNode root) {
    int[] a = solve(root);
    return Math.max(a[0], a[1]);
}

# Return (rob, notRob); collapse to max only at the root.
def rob(root):
    def solve(node):
        if not node:
            return (0, 0)
        lr, ln = solve(node.left)
        rr, rn = solve(node.right)
        do_rob = node.val + ln + rn           # rob node -> skip children
        skip   = max(lr, ln) + max(rr, rn)    # skip node -> children free
        return (do_rob, skip)
    return max(solve(root))

// 3-state greedy: camera only when a child is uncovered.
int cameras = 0;
int dfs(TreeNode* node) {          // 0 uncovered, 1 covered, 2 has camera
    if (!node) return 1;           // null counts as covered
    int l = dfs(node->left), r = dfs(node->right);
    if (l == 0 || r == 0) { cameras++; return 2; }  // must cover a child
    if (l == 2 || r == 2) return 1;                 // a child's camera covers us
    return 0;                                        // uncovered -> parent handles
}
int minCameraCover(TreeNode* root) {
    cameras = 0;
    if (dfs(root) == 0) cameras++;  // root left uncovered
    return cameras;
}

// 3-state greedy: camera only when a child is uncovered.
int cameras = 0;
int dfs(TreeNode node) {           // 0 uncovered, 1 covered, 2 has camera
    if (node == null) return 1;    // null counts as covered
    int l = dfs(node.left), r = dfs(node.right);
    if (l == 0 || r == 0) { cameras++; return 2; }  // must cover a child
    if (l == 2 || r == 2) return 1;                 // a child's camera covers us
    return 0;                                       // uncovered: parent's job
}
public int minCameraCover(TreeNode root) {
    return (dfs(root) == 0 ? 1 : 0) + cameras;      // root uncovered? one more
}

# 3-state greedy: camera only when a child is uncovered.
def minCameraCover(root):
    cameras = 0
    def dfs(node):                 # 0 uncovered, 1 covered, 2 has camera
        nonlocal cameras
        if not node:
            return 1               # null counts as covered
        l, r = dfs(node.left), dfs(node.right)
        if l == 0 or r == 0:
            cameras += 1; return 2  # must cover an uncovered child
        if l == 2 or r == 2:
            return 1                # a child's camera covers us
        return 0                    # uncovered -> parent handles it
    if dfs(root) == 0:
        cameras += 1                # root left uncovered
    return cameras