树上路径与递归汇总

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

from collections import defaultdict


def path_sum_count(root, target: int) -> int:
    """Downward paths, starting and ending anywhere, whose values sum to target (LC 437)."""
    seen = defaultdict(int)  # prefix sums on the current root-to-node path
    seen[0] = 1
    count = 0

    def dfs(node, pre: int) -> None:
        nonlocal count
        if not node:
            return
        pre += node.val
        count += seen[pre - target]  # a path ending here starts after an ancestor's prefix
        seen[pre] += 1
        dfs(node.left, pre)
        dfs(node.right, pre)
        seen[pre] -= 1  # leaving node: its prefix is off the path now

    dfs(root, 0)
    return count

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// Downward paths, starting and ending anywhere, whose values sum to target (LC 437).
int pathSumCount(TreeNode* root, long long target) {
    unordered_map<long long, int> seen{{0, 1}};  // prefix sums on the current root-to-node path
    int count = 0;
    function<void(TreeNode*, long long)> dfs = [&](TreeNode* node, long long pre) {
        if (!node) return;
        pre += node->val;
        if (auto it = seen.find(pre - target); it != seen.end()) count += it->second;  // starts after an ancestor's prefix
        seen[pre]++;
        dfs(node->left, pre);
        dfs(node->right, pre);
        seen[pre]--;  // leaving node: its prefix is off the path now
    };
    dfs(root, 0);
    return count;
}

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    private final Map<Long, Integer> seen = new HashMap<>(); // prefix sums on the current root-to-node path
    private int count;

    // Downward paths, starting and ending anywhere, whose values sum to target (LC 437).
    int pathSumCount(TreeNode root, long target) {
        seen.clear();
        seen.put(0L, 1);
        count = 0;
        dfs(root, 0, target);
        return count;
    }

    private void dfs(TreeNode node, long pre, long target) {
        if (node == null) return;
        pre += node.val;
        count += seen.getOrDefault(pre - target, 0); // a path ending here starts after an ancestor's prefix
        seen.merge(pre, 1, Integer::sum);
        dfs(node.left, pre, target);
        dfs(node.right, pre, target);
        seen.merge(pre, -1, Integer::sum); // leaving node: its prefix is off the path now
    }
}

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// pathSumCount counts downward paths, starting and ending anywhere, that sum to target (LC 437).
func pathSumCount(root *TreeNode, target int) int {
	seen := map[int]int{0: 1} // prefix sums on the current root-to-node path
	count := 0
	var dfs func(node *TreeNode, pre int)
	dfs = func(node *TreeNode, pre int) {
		if node == nil {
			return
		}
		pre += node.Val
		count += seen[pre-target] // a path ending here starts after an ancestor's prefix
		seen[pre]++
		dfs(node.Left, pre)
		dfs(node.Right, pre)
		seen[pre]-- // leaving node: its prefix is off the path now
	}
	dfs(root, 0)
	return count
}

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def lowest_common_ancestor(root, p, q):
    """Deepest node with both p and q in its subtree, a node counting as its own descendant (LC 236)."""
    if not root or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:  # p and q are on different sides: they meet here
        return root
    return left or right

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// Deepest node with both p and q in its subtree, a node counting as its own descendant (LC 236).
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;  // p and q are on different sides: they meet here
    return left ? left : right;
}

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Deepest node with both p and q in its subtree, a node counting as its own descendant (LC 236).
    TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root; // p and q are on different sides: they meet here
        return left != null ? left : right;
    }
}

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// lowestCommonAncestor returns the deepest node with both p and q in its subtree (LC 236).
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil { // p and q are on different sides: they meet here
		return root
	}
	if left != nil {
		return left
	}
	return right
}