// Height = 1 + the taller subtree; empty = 0.
int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

// Height = 1 + the taller subtree; empty = 0.
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

# Height = 1 + the taller subtree; empty = 0.
def maxDepth(root):
    if root is None:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

// Height helper returns -1 as an 'unbalanced below' sentinel.
int height(TreeNode* node) {
    if (node == nullptr) return 0;
    int l = height(node->left);
    if (l == -1) return -1;
    int r = height(node->right);
    if (r == -1) return -1;
    if (abs(l - r) > 1) return -1;        // unbalanced here
    return 1 + max(l, r);
}
bool isBalanced(TreeNode* root) {
    return height(root) != -1;
}

// Height helper returns -1 as an 'unbalanced below' sentinel.
int height(TreeNode node) {
    if (node == null) return 0;
    int l = height(node.left);
    if (l == -1) return -1;                  // bail out early
    int r = height(node.right);
    if (r == -1) return -1;
    if (Math.abs(l - r) > 1) return -1;      // -1 can never be a real height
    return 1 + Math.max(l, r);
}
public boolean isBalanced(TreeNode root) {
    return height(root) != -1;               // one postorder pass, O(n)
}

# Height helper returns -1 as an 'unbalanced below' sentinel.
def isBalanced(root):
    def height(node):
        if node is None:
            return 0
        l = height(node.left)
        if l == -1:
            return -1
        r = height(node.right)
        if r == -1:
            return -1
        if abs(l - r) > 1:                 # unbalanced here
            return -1
        return 1 + max(l, r)
    return height(root) != -1

// Return height; update the global diameter with leftH + rightH.
int best = 0;
int height(TreeNode* node) {
    if (node == nullptr) return 0;
    int l = height(node->left);
    int r = height(node->right);
    best = max(best, l + r);              // longest path bending at node (edges)
    return 1 + max(l, r);                 // RETURN height, not diameter
}
int diameterOfBinaryTree(TreeNode* root) {
    best = 0; height(root); return best;
}

// Return height; update the global diameter with leftH + rightH.
int best = 0;
int height(TreeNode node) {
    if (node == null) return 0;
    int l = height(node.left);
    int r = height(node.right);
    best = Math.max(best, l + r);            // longest path BENDING here
    return 1 + Math.max(l, r);               // what the parent needs
}
public int diameterOfBinaryTree(TreeNode root) {
    height(root);
    return best;
}

# Return height; update the global diameter with leftH + rightH.
def diameterOfBinaryTree(root):
    best = 0
    def height(node):
        nonlocal best
        if node is None:
            return 0
        l = height(node.left)
        r = height(node.right)
        best = max(best, l + r)           # longest path bending at node (edges)
        return 1 + max(l, r)              # RETURN height, not diameter
    height(root)
    return best

// Clamp child gains to 0; track val+L+R, return val+max(L,R).
int best = INT_MIN;
int gain(TreeNode* node) {
    if (node == nullptr) return 0;
    int l = max(0, gain(node->left));    // drop a negative branch
    int r = max(0, gain(node->right));
    best = max(best, node->val + l + r); // best path bending at this node
    return node->val + max(l, r);        // a path continues up via ONE child
}
int maxPathSum(TreeNode* root) {
    best = INT_MIN; gain(root); return best;
}

// Clamp child gains to 0; track val+L+R, return val+max(L,R).
int best = Integer.MIN_VALUE;
int gain(TreeNode node) {
    if (node == null) return 0;
    int l = Math.max(0, gain(node.left));    // drop a negative branch
    int r = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + l + r); // a path PEAKING here
    return node.val + Math.max(l, r);        // upward: only one side
}
public int maxPathSum(TreeNode root) {
    gain(root);
    return best;
}

# Clamp child gains to 0; track val+L+R, return val+max(L,R).
def maxPathSum(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if node is None:
            return 0
        l = max(0, gain(node.left))      # drop a negative branch
        r = max(0, gain(node.right))
        best = max(best, node.val + l + r)  # best path bending here
        return node.val + max(l, r)      # continue up via ONE child
    gain(root)
    return best

// Compare two trees in lockstep.
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;            // both empty -> match
    if (!p || !q || p->val != q->val) return false;
    return isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}

// Compare two trees in lockstep.
public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;      // both empty -> match
    if (p == null || q == null || p.val != q.val) return false;
    return isSameTree(p.left, q.left)
        && isSameTree(p.right, q.right);
}

# Compare two trees in lockstep.
def isSameTree(p, q):
    if not p and not q:                   # both empty -> match
        return True
    if not p or not q or p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

// Mirror check: cross-pair the children.
bool isMirror(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;
    if (!a || !b || a->val != b->val) return false;
    return isMirror(a->left, b->right)   // OUTER pair
        && isMirror(a->right, b->left);  // INNER pair
}
bool isSymmetric(TreeNode* root) {
    return !root || isMirror(root->left, root->right);
}

// Mirror check: cross-pair the children.
boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null || a.val != b.val) return false;
    return isMirror(a.left, b.right)         // OUTER pair
        && isMirror(a.right, b.left);        // INNER pair
}
public boolean isSymmetric(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}

# Mirror check: cross-pair the children.
def isSymmetric(root):
    def isMirror(a, b):
        if not a and not b:
            return True
        if not a or not b or a.val != b.val:
            return False
        return isMirror(a.left, b.right) and isMirror(a.right, b.left)
    return not root or isMirror(root.left, root.right)

// Swap children at every node.
TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

// Swap children at every node.
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode t = root.left; root.left = root.right; root.right = t;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

# Swap children at every node.
def invertTree(root):
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

// Level order; reverse the placement on alternate levels.
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    bool leftToRight = true;
    while (!q.empty()) {
        int n = q.size();
        vector<int> level(n);
        for (int i = 0; i < n; i++) {
            TreeNode* node = q.front(); q.pop();
            int idx = leftToRight ? i : n - 1 - i;   // place, don't reorder queue
            level[idx] = node->val;
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        leftToRight = !leftToRight;
        res.push_back(level);
    }
    return res;
}

// Level order; reverse the placement on alternate levels.
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    boolean leftToRight = true;

    while (!q.isEmpty()) {
        int n = q.size();                    // exactly this level
        Integer[] level = new Integer[n];
        for (int i = 0; i < n; i++) {
            TreeNode node = q.poll();
            level[leftToRight ? i : n - 1 - i] = node.val;   // place, do not push
            if (node.left  != null) q.add(node.left);        // ALWAYS left first
            if (node.right != null) q.add(node.right);
        }
        res.add(Arrays.asList(level));
        leftToRight = !leftToRight;
    }
    return res;
}

# Level order; reverse the placement on alternate levels.
from collections import deque
def zigzagLevelOrder(root):
    res = []
    if not root:
        return res
    q = deque([root])
    left_to_right = True
    while q:
        n = len(q)
        level = [0] * n
        for i in range(n):
            node = q.popleft()
            idx = i if left_to_right else n - 1 - i     # place, don't reorder queue
            level[idx] = node.val
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        left_to_right = not left_to_right
        res.append(level)
    return res

// The last node popped in each BFS level is the rightmost.
vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            TreeNode* node = q.front(); q.pop();
            if (i == n - 1) res.push_back(node->val);   // rightmost of level
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return res;
}

// The last node popped in each BFS level is the rightmost.
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.add(root);

    while (!q.isEmpty()) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            TreeNode node = q.poll();
            if (i == n - 1) res.add(node.val);       // the LAST of this level
            if (node.left  != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
    }
    return res;
}

# The last node popped in each BFS level is the rightmost.
from collections import deque
def rightSideView(root):
    res = []
    if not root:
        return res
    q = deque([root])
    while q:
        n = len(q)
        for i in range(n):
            node = q.popleft()
            if i == n - 1:                    # rightmost of level
                res.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
    return res

// Perfect tree: wire level L+1 using level L's next chain. O(1) space.
Node* connect(Node* root) {
    Node* leftmost = root;
    while (leftmost && leftmost->left) {
        Node* node = leftmost;
        while (node) {
            node->left->next = node->right;
            node->right->next = node->next ? node->next->left : nullptr;
            node = node->next;               // walk the current level
        }
        leftmost = leftmost->left;           // drop to the next level
    }
    return root;
}

// Perfect tree: wire level L+1 using level L's next chain. O(1) space.
public Node connect(Node root) {
    Node leftmost = root;
    while (leftmost != null && leftmost.left != null) {
        Node node = leftmost;
        while (node != null) {
            node.left.next = node.right;             // within this parent
            if (node.next != null)
                node.right.next = node.next.left;    // across to the neighbour
            node = node.next;                        // walk level L via next
        }
        leftmost = leftmost.left;                    // drop to level L+1
    }
    return root;
}

# Perfect tree: wire level L+1 using level L's next chain. O(1) space.
def connect(root):
    leftmost = root
    while leftmost and leftmost.left:
        node = leftmost
        while node:
            node.left.next = node.right
            node.right.next = node.next.left if node.next else None
            node = node.next                 # walk the current level
        leftmost = leftmost.left             # drop to the next level
    return root

// BFS carrying (row, col); bucket by column, sort by (row, val).
vector<vector<int>> verticalTraversal(TreeNode* root) {
    map<int, vector<pair<int,int>>> cols;        // col -> (row, val)
    queue<tuple<TreeNode*,int,int>> q;
    q.push({root, 0, 0});
    while (!q.empty()) {
        auto [node, row, col] = q.front(); q.pop();
        cols[col].push_back({row, node->val});
        if (node->left)  q.push({node->left,  row + 1, col - 1});
        if (node->right) q.push({node->right, row + 1, col + 1});
    }
    vector<vector<int>> res;
    for (auto& [col, vec] : cols) {
        sort(vec.begin(), vec.end());            // by row, then value
        vector<int> colVals;
        for (auto& [row, val] : vec) colVals.push_back(val);
        res.push_back(colVals);
    }
    return res;
}

// BFS carrying (row, col); bucket by column, sort by (row, val).
public List<List<Integer>> verticalTraversal(TreeNode root) {
    // TreeMap keeps the columns in left-to-right order for free
    TreeMap<Integer, List<int[]>> cols = new TreeMap<>();
    Queue<Object[]> q = new ArrayDeque<>();
    if (root != null) q.add(new Object[]{root, 0, 0});

    while (!q.isEmpty()) {
        Object[] cur = q.poll();
        TreeNode node = (TreeNode) cur[0];
        int row = (int) cur[1], col = (int) cur[2];
        cols.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val});
        if (node.left  != null) q.add(new Object[]{node.left,  row + 1, col - 1});
        if (node.right != null) q.add(new Object[]{node.right, row + 1, col + 1});
    }
    List<List<Integer>> res = new ArrayList<>();
    for (List<int[]> bucket : cols.values()) {
        // same column: by row, then by VALUE - that tie-break is the spec
        bucket.sort((x, y) -> x[0] != y[0] ? x[0] - y[0] : x[1] - y[1]);
        List<Integer> out = new ArrayList<>();
        for (int[] e : bucket) out.add(e[1]);
        res.add(out);
    }
    return res;
}

# BFS carrying (row, col); bucket by column, sort by (row, val).
from collections import deque, defaultdict
def verticalTraversal(root):
    cols = defaultdict(list)                      # col -> list of (row, val)
    q = deque([(root, 0, 0)])
    while q:
        node, row, col = q.popleft()
        cols[col].append((row, node.val))
        if node.left:  q.append((node.left,  row + 1, col - 1))
        if node.right: q.append((node.right, row + 1, col + 1))
    res = []
    for col in sorted(cols):
        res.append([val for row, val in sorted(cols[col])])   # by row, then value
    return res

// Heap indices; normalise per level to avoid overflow.
int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    int best = 0;
    queue<pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    while (!q.empty()) {
        int n = q.size();
        unsigned long long first = q.front().second, last = first;
        for (int i = 0; i < n; i++) {
            auto [node, idx] = q.front(); q.pop();
            idx -= first;                        // re-base to avoid overflow
            last = idx;
            if (node->left)  q.push({node->left,  2 * idx});
            if (node->right) q.push({node->right, 2 * idx + 1});
        }
        best = max(best, (int)(last + 1));
    }
    return best;
}

// Heap indices; normalise per level to avoid overflow.
public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int best = 0;
    Queue<Object[]> q = new ArrayDeque<>();
    q.add(new Object[]{root, 0});

    while (!q.isEmpty()) {
        int n = q.size();
        int first = 0, last = 0;
        long base = (long) q.peek()[1];      // re-base: indices double per level
        for (int i = 0; i < n; i++) {
            Object[] cur = q.poll();
            TreeNode node = (TreeNode) cur[0];
            int idx = (int) ((long) cur[1] - base);
            if (i == 0) first = idx;
            if (i == n - 1) last = idx;
            if (node.left  != null) q.add(new Object[]{node.left,  2L * idx});
            if (node.right != null) q.add(new Object[]{node.right, 2L * idx + 1});
        }
        best = Math.max(best, last - first + 1);   // counts the null GAPS too
    }
    return best;
}

# Heap indices; normalise per level to avoid overflow.
from collections import deque
def widthOfBinaryTree(root):
    if not root:
        return 0
    best = 0
    q = deque([(root, 0)])
    while q:
        n = len(q)
        first = q[0][1]
        last = first
        for _ in range(n):
            node, idx = q.popleft()
            idx -= first                          # re-base to avoid overflow
            last = idx
            if node.left:  q.append((node.left,  2 * idx))
            if node.right: q.append((node.right, 2 * idx + 1))
        best = max(best, last + 1)
    return best

// Carry the path down; emit it at each leaf.
void dfs(TreeNode* node, string path, vector<string>& res) {
    if (!node) return;
    path += to_string(node->val);
    if (!node->left && !node->right) { res.push_back(path); return; }
    path += "->";
    dfs(node->left, path, res);
    dfs(node->right, path, res);
}
vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> res; dfs(root, "", res); return res;
}

// Carry the path down; emit it at each leaf.
void dfs(TreeNode node, String path, List<String> res) {
    if (node == null) return;
    path += node.val;
    if (node.left == null && node.right == null) { res.add(path); return; }
    path += "->";
    dfs(node.left,  path, res);              // String is immutable, so each
    dfs(node.right, path, res);              // branch gets its own copy free
}

# Carry the path down; emit it at each leaf.
def binaryTreePaths(root):
    res = []
    def dfs(node, path):
        if not node:
            return
        path = path + str(node.val)
        if not node.left and not node.right:
            res.append(path); return
        path += "->"
        dfs(node.left, path)
        dfs(node.right, path)
    dfs(root, "")
    return res

// Root-to-leaf sum == target: subtract down, check at leaves.
bool hasPathSum(TreeNode* node, int target) {
    if (!node) return false;
    if (!node->left && !node->right) return target == node->val;
    return hasPathSum(node->left,  target - node->val)
        || hasPathSum(node->right, target - node->val);
}

// Root-to-leaf sum == target: subtract down, check at leaves.
public boolean hasPathSum(TreeNode node, int target) {
    if (node == null) return false;
    if (node.left == null && node.right == null) return target == node.val;
    return hasPathSum(node.left,  target - node.val)
        || hasPathSum(node.right, target - node.val);
}

# Root-to-leaf sum == target: subtract down, check at leaves.
def hasPathSum(node, target):
    if not node:
        return False
    if not node.left and not node.right:
        return target == node.val
    return (hasPathSum(node.left,  target - node.val)
            or hasPathSum(node.right, target - node.val))

// Backtracking: push, recurse, pop; record a copy at a matching leaf.
void dfs(TreeNode* node, int target, vector<int>& path,
         vector<vector<int>>& res) {
    if (!node) return;
    path.push_back(node->val);
    target -= node->val;
    if (!node->left && !node->right && target == 0)
        res.push_back(path);                 // a copy of the current path
    else {
        dfs(node->left,  target, path, res);
        dfs(node->right, target, path, res);
    }
    path.pop_back();                         // backtrack
}
vector<vector<int>> pathSum(TreeNode* root, int target) {
    vector<vector<int>> res; vector<int> path;
    dfs(root, target, path, res); return res;
}

// Backtracking: push, recurse, pop; record a copy at a matching leaf.
void dfs(TreeNode node, int target, List<Integer> path, List<List<Integer>> res) {
    if (node == null) return;
    path.add(node.val);
    target -= node.val;
    if (node.left == null && node.right == null && target == 0)
        res.add(new ArrayList<>(path));      // a COPY: path keeps mutating
    dfs(node.left,  target, path, res);
    dfs(node.right, target, path, res);
    path.remove(path.size() - 1);            // undo before the sibling
}

# Backtracking: push, recurse, pop; record a copy at a matching leaf.
def pathSum(root, target):
    res, path = [], []
    def dfs(node, target):
        if not node:
            return
        path.append(node.val)
        target -= node.val
        if not node.left and not node.right and target == 0:
            res.append(path[:])              # a COPY of the current path
        else:
            dfs(node.left, target)
            dfs(node.right, target)
        path.pop()                           # backtrack
    dfs(root, target)
    return res

// Prefix-sum count: paths ending here with sum target.
int total = 0;
void dfs(TreeNode* node, long running, long target,
         unordered_map<long,int>& seen) {
    if (!node) return;
    running += node->val;
    total += seen.count(running - target) ? seen[running - target] : 0;
    seen[running]++;
    dfs(node->left, running, target, seen);
    dfs(node->right, running, target, seen);
    seen[running]--;                          // backtrack the map
}
int pathSum(TreeNode* root, int target) {
    total = 0; unordered_map<long,int> seen{{0,1}};
    dfs(root, 0, target, seen); return total;
}

// Prefix-sum count: paths ending here with sum target.
int total = 0;
void dfs(TreeNode node, long running, long target, Map<Long,Integer> seen) {
    if (node == null) return;
    running += node.val;
    total += seen.getOrDefault(running - target, 0);   // starts that qualify
    seen.merge(running, 1, Integer::sum);
    dfs(node.left,  running, target, seen);
    dfs(node.right, running, target, seen);
    seen.merge(running, -1, Integer::sum);   // leave the path as you found it
}
public int pathSum(TreeNode root, int target) {
    Map<Long,Integer> seen = new HashMap<>();
    seen.put(0L, 1);                         // the empty prefix
    dfs(root, 0, target, seen);
    return total;
}

# Prefix-sum count: paths ending here with sum target.
from collections import defaultdict
def pathSum(root, target):
    seen = defaultdict(int); seen[0] = 1
    total = 0
    def dfs(node, running):
        nonlocal total
        if not node:
            return
        running += node.val
        total += seen[running - target]
        seen[running] += 1
        dfs(node.left, running)
        dfs(node.right, running)
        seen[running] -= 1                     # backtrack the map
    dfs(root, 0)
    return total

// Both subtrees report a target -> this node is the LCA.
TreeNode* lowestCommonAncestor(TreeNode* node, TreeNode* p, TreeNode* q) {
    if (!node || node == p || node == q) return node;
    TreeNode* left  = lowestCommonAncestor(node->left, p, q);
    TreeNode* right = lowestCommonAncestor(node->right, p, q);
    if (left && right) return node;          // p and q on different sides
    return left ? left : right;              // both on one side (or neither)
}

// Both subtrees report a target -> this node is the LCA.
public TreeNode lowestCommonAncestor(TreeNode node, TreeNode p, TreeNode q) {
    if (node == null || node == p || node == q) return node;
    TreeNode left  = lowestCommonAncestor(node.left,  p, q);
    TreeNode right = lowestCommonAncestor(node.right, p, q);
    if (left != null && right != null) return node;   // one each side
    return (left != null) ? left : right;             // propagate the finding
}

# Both subtrees report a target -> this node is the LCA.
def lowestCommonAncestor(node, p, q):
    if not node or node == p or node == q:
        return node
    left  = lowestCommonAncestor(node.left, p, q)
    right = lowestCommonAncestor(node.right, p, q)
    if left and right:                        # p and q on different sides
        return node
    return left if left else right

// Parent map turns the tree into a graph; BFS K layers from target.
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
    unordered_map<TreeNode*, TreeNode*> parent;
    function<void(TreeNode*, TreeNode*)> mark = [&](TreeNode* n, TreeNode* p) {
        if (!n) return; parent[n] = p; mark(n->left, n); mark(n->right, n);
    };
    mark(root, nullptr);
    queue<TreeNode*> q; q.push(target);
    unordered_set<TreeNode*> seen{target};
    int dist = 0;
    while (!q.empty()) {
        if (dist == K) {
            vector<int> res;
            while (!q.empty()) { res.push_back(q.front()->val); q.pop(); }
            return res;
        }
        int n = q.size();
        for (int i = 0; i < n; i++) {
            TreeNode* node = q.front(); q.pop();
            for (TreeNode* nb : {node->left, node->right, parent[node]})
                if (nb && !seen.count(nb)) { seen.insert(nb); q.push(nb); }
        }
        dist++;
    }
    return {};
}

// Parent map turns the tree into a graph; BFS K layers from target.
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    mark(root, null, parent);

    Queue<TreeNode> q = new ArrayDeque<>();
    Set<TreeNode> seen = new HashSet<>();     // the graph is UNDIRECTED now
    q.add(target); seen.add(target);
    int dist = 0;

    while (!q.isEmpty()) {
        if (dist == K) {
            List<Integer> res = new ArrayList<>();
            for (TreeNode n : q) res.add(n.val);
            return res;
        }
        int n = q.size();
        for (int i = 0; i < n; i++) {
            TreeNode cur = q.poll();
            for (TreeNode nx : new TreeNode[]{cur.left, cur.right, parent.get(cur)})
                if (nx != null && seen.add(nx)) q.add(nx);   // add() reports new
        }
        dist++;
    }
    return new ArrayList<>();
}
private void mark(TreeNode n, TreeNode p, Map<TreeNode, TreeNode> parent) {
    if (n == null) return;
    parent.put(n, p);
    mark(n.left, n, parent);
    mark(n.right, n, parent);
}

# Parent map turns the tree into a graph; BFS K layers from target.
from collections import deque
def distanceK(root, target, K):
    parent = {}
    def mark(n, p):
        if not n: return
        parent[n] = p; mark(n.left, n); mark(n.right, n)
    mark(root, None)
    q = deque([target]); seen = {target}; dist = 0
    while q:
        if dist == K:
            return [node.val for node in q]
        for _ in range(len(q)):
            node = q.popleft()
            for nb in (node.left, node.right, parent[node]):
                if nb and nb not in seen:
                    seen.add(nb); q.append(nb)
        dist += 1
    return []