Finding the Bottom Left Tree Value

Locating the leftmost value in the last row of a binary tree can be efficiently achieved using Breadth-First Search (BFS). By processing the tree level by level, the first node encountered at each depth represents the leftmost node for that specific row. Upon completing the traversal, the value recorded for the first node of the final processed level is the desired bottom-left value.

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return -1;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.offer(root);
        int bottomLeft = root.val;
        
        while (!nodeQueue.isEmpty()) {
            int levelSize = nodeQueue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode current = nodeQueue.poll();
                if (i == 0) {
                    bottomLeft = current.val;
                }
                if (current.left != null) nodeQueue.offer(current.left);
                if (current.right != null) nodeQueue.offer(current.right);
            }
        }
        return bottomLeft;
    }
}

Verifying Path Sum Existence

Determining if a root-to-leaf path exists where the sum of node values equals a target can be implemented via Depth-First Search (DFS). Instead of accumulating the sum downwards, subtracting the current node's value from the target sum simplifies the logic. When a leaf node is reached, the path is valid if the remaining target matches the leaf's value.

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        int remaining = targetSum - root.val;
        return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
    }
}

Collecting All Path Sums

Unlike simply verifying existence, finding all root-to-leaf paths that sum to a given target requires backtracking. A list is maintained to track the current traversal path. Upon reaching a leaf node where the remaining sum equals the node's value, a deep copy of the current path is stored. After exploring both subtrees, the current node is removed from the path to backtrack and explore alternative branches.

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> validPaths = new ArrayList<>();
        traverse(root, targetSum, new ArrayList<>(), validPaths);
        return validPaths;
    }

    private void traverse(TreeNode node, int remaining, List<Integer> currentPath, List<List<Integer>> validPaths) {
        if (node == null) return;
        
        currentPath.add(node.val);
        if (node.left == null && node.right == null && remaining == node.val) {
            validPaths.add(new ArrayList<>(currentPath));
        } else {
            traverse(node.left, remaining - node.val, currentPath, validPaths);
            traverse(node.right, remaining - node.val, currentPath, validPaths);
        }
        currentPath.remove(currentPath.size() - 1);
    }
}

Constructing Trees from Inorder and Postorder Traversals

Reconstructing a binary tree from its inorder and postorder traversal arrays relies on identifying the root from the postorder array and partitioning the inorder array accordingly. The last element in the postorder array always represents the root. By locating this root within the inorder array using a hash map for constant-time lookups, the array is split into left and right subtrees. The subtree sizes derived from the inorder partition are then used to accurately slice the postorder array, allowing recursive construction of both left and right children.

class Solution {
    private Map<Integer, Integer> inorderMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return construct(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode construct(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) return null;

        int rootVal = postorder[postEnd];
        TreeNode rootNode = new TreeNode(rootVal);
        int rootInIdx = inorderMap.get(rootVal);
        int leftSubtreeSize = rootInIdx - inStart;

        rootNode.left = construct(inorder, inStart, rootInIdx - 1, postorder, postStart, postStart + leftSubtreeSize - 1);
        rootNode.right = construct(inorder, rootInIdx + 1, inEnd, postorder, postStart + leftSubtreeSize, postEnd - 1);

        return rootNode;
    }
}