跳转至

3879. 二叉树中的最大不同路径和 🔒

题目描述

给定一棵 二叉树 的 root，其中每个节点包含一个整数值。

树中的 有效 路径是指一系列 相连 的节点，使得：

  • 路径可以在树中的 任意节点 开始和结束。
  • 路径 不 需要经过根节点。
  • 路径上的所有节点值都是 不同 的。

返回一个整数，表示所有有效路径中节点值的 最大 可能总和。

 

示例 1：

输入：root = [2,2,1]

输出：3

解释：

  • 路径 2 → 2 是无效的，因为值 2 不唯一。
  • 最大和的有效路径是 2 → 1，其和 = 2 + 1 = 3。

示例 2：

输入：root = [1,-2,5,null,null,3,5]

输出：9

解释：

  • 路径 3 → 5 → 5 是无效的，因为值 5 不唯一。
  • 最大和的有效路径是 1 → 5 → 3，其和 = 1 + 5 + 3 = 9。

示例 3：

输入：root = [4,6,6,null,null,null,9]

输出：19

解释：

  • 路径 6 → 4 → 6 → 9 是无效的，因为值 6 出现了多次。
  • 最大和的有效路径是 4 → 6 → 9，其和 = 4 + 6 + 9 = 19。

 

提示：

  • 树中的节点数范围为 [1, 1000]。
  • -1000 <= Node.val <= 1000​​​​​​​

解法

方法一：DFS + 哈希表

我们可以将树看成一个无向图，使用一个哈希表 \(g\) 来存储每个节点的相邻节点，其中 \(g[node]\) 包含节点 \(node\) 的父节点、左子节点和右子节点。

我们使用深度优先搜索来遍历树，并构建哈希表 \(g\)。对于每个节点，我们将其父节点、左子节点和右子节点添加到 \(g[node]\) 中。

接下来，我们使用另一个深度优先搜索来计算以每个节点为起点的最大路径和。在这个过程中，我们使用一个哈希集合 \(vis\) 来记录当前路径上已经访问过的节点值，以确保路径上的节点值都是不同的。对于每个节点，我们首先检查它是否已经在 \(vis\) 中，如果是，则返回 0。否则，我们将节点值添加到 \(vis\) 中，并计算以该节点为起点的路径和。我们遍历 \(g[node]\) 中的相邻节点，递归地计算以相邻节点为起点的路径和，并更新当前节点的路径和。最后，我们将当前节点值从 \(vis\) 中移除，并返回当前节点值加上最佳路径和。

我们对树中的每个节点执行上述计算，并记录最大路径和。最终返回最大路径和作为答案。

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是树中的节点数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxSum(self, root: Optional[TreeNode]) -> int:
        def dfs(node, p):
            if node is None:
                return
            g[node].append(p)
            g[node].append(node.left)
            g[node].append(node.right)
            dfs(node.left, node)
            dfs(node.right, node)

        def dfs2(node):
            if node is None or node.val in vis:
                return 0
            vis.add(node.val)
            res = node.val
            best = 0
            for nxt in g[node]:
                best = max(best, dfs2(nxt))
            vis.remove(node.val)
            res += best
            return res

        g = defaultdict(list)
        dfs(root, None)
        vis = set()
        ans = -inf
        for node in g:
            ans = max(ans, dfs2(node))
            vis.clear()
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<TreeNode, List<TreeNode>> g = new HashMap<>();
    Set<Integer> vis = new HashSet<>();

    public int maxSum(TreeNode root) {
        dfs(root, null);

        int ans = Integer.MIN_VALUE;
        for (TreeNode node : g.keySet()) {
            ans = Math.max(ans, dfs2(node));
            vis.clear();
        }
        return ans;
    }

    private void dfs(TreeNode node, TreeNode p) {
        if (node == null) {
            return;
        }
        g.computeIfAbsent(node, k -> new ArrayList<>());
        g.get(node).add(p);
        g.get(node).add(node.left);
        g.get(node).add(node.right);

        dfs(node.left, node);
        dfs(node.right, node);
    }

    private int dfs2(TreeNode node) {
        if (node == null || vis.contains(node.val)) {
            return 0;
        }
        vis.add(node.val);
        int res = node.val;
        int best = 0;
        for (TreeNode nxt : g.getOrDefault(node, Collections.emptyList())) {
            best = Math.max(best, dfs2(nxt));
        }
        vis.remove(node.val);
        return res + best;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxSum(TreeNode* root) {
        unordered_map<TreeNode*, vector<TreeNode*>> g;
        unordered_set<int> vis;

        auto dfs = [&](this auto&& dfs, TreeNode* node, TreeNode* p) -> void {
            if (!node) return;
            g[node].push_back(p);
            g[node].push_back(node->left);
            g[node].push_back(node->right);
            dfs(node->left, node);
            dfs(node->right, node);
        };

        auto dfs2 = [&](this auto&& dfs2, TreeNode* node) -> int {
            if (!node || vis.count(node->val)) return 0;
            vis.insert(node->val);
            int res = node->val;
            int best = 0;
            for (auto nxt : g[node]) {
                best = max(best, dfs2(nxt));
            }
            vis.erase(node->val);
            return res + best;
        };

        dfs(root, nullptr);

        int ans = INT_MIN;
        for (auto& [node, _] : g) {
            ans = max(ans, dfs2(node));
            vis.clear();
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxSum(root *TreeNode) int {
    g := map[*TreeNode][]*TreeNode{}

    var dfs func(node, p *TreeNode)
    dfs = func(node, p *TreeNode) {
        if node == nil {
            return
        }
        g[node] = append(g[node], p, node.Left, node.Right)
        dfs(node.Left, node)
        dfs(node.Right, node)
    }

    vis := map[int]bool{}

    var dfs2 func(node *TreeNode) int
    dfs2 = func(node *TreeNode) int {
        if node == nil || vis[node.Val] {
            return 0
        }
        vis[node.Val] = true
        res := node.Val
        best := 0
        for _, nxt := range g[node] {
            if v := dfs2(nxt); v > best {
                best = v
            }
        }
        vis[node.Val] = false
        return res + best
    }

    dfs(root, nil)

    ans := math.MinInt
    for node := range g {
        ans = max(ans, dfs2(node))
        clear(vis)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function maxSum(root: TreeNode | null): number {
    const g = new Map<TreeNode, (TreeNode | null)[]>();

    function dfs(node: TreeNode | null, p: TreeNode | null): void {
        if (!node) return;
        if (!g.has(node)) g.set(node, []);
        g.get(node)!.push(p, node.left, node.right);
        dfs(node.left, node);
        dfs(node.right, node);
    }

    const vis = new Set<number>();

    function dfs2(node: TreeNode | null): number {
        if (!node || vis.has(node.val)) return 0;
        vis.add(node.val);
        let res = node.val;
        let best = 0;
        for (const nxt of g.get(node) || []) {
            best = Math.max(best, dfs2(nxt));
        }
        vis.delete(node.val);
        return res + best;
    }

    dfs(root, null);

    let ans = -Infinity;
    for (const node of g.keys()) {
        ans = Math.max(ans, dfs2(node));
        vis.clear();
    }
    return ans;
}

评论