# 143. 最长同值路径

本题两个考点：

层序遍历构造二叉树
树形dp，找出最长路径

对于写代码不多，或者动手能力比较差的录友，第一个构造二叉树基本就被卡主了。

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 根据层序遍历数组构建二叉树
TreeNode* constructBinaryTree(const vector<string>& levelOrder) {
    if (levelOrder.empty()) return NULL;

    TreeNode* root = new TreeNode(stoi(levelOrder[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;

    while (!q.empty() && i < levelOrder.size()) {
        TreeNode* current = q.front();
        q.pop();

        if (i < levelOrder.size() && levelOrder[i] != "null") {
            current->left = new TreeNode(stoi(levelOrder[i]));
            q.push(current->left);
        }
        i++;

        if (i < levelOrder.size() && levelOrder[i] != "null") {
            current->right = new TreeNode(stoi(levelOrder[i]));
            q.push(current->right);
        }
        i++;
    }

    return root;
}

int result = 0;

// 树形DP
int dfs(TreeNode* node) {
    if (node == NULL) return 0;
    int leftPath = dfs(node->left);
    int rightPath = dfs(node->right);

    int leftNum = 0, rightNum = 0;
    if (node->left != NULL && node->left->val == node->val) {
        leftNum = leftPath + 1;
    }
    if (node->right != NULL && node->right->val == node->val) {
        rightNum = rightPath + 1;
    }
    result = max(result, leftNum + rightNum);
    return max(leftNum, rightNum);

}


int main() {
    int n;
    cin >> n;
    vector<string> levelOrder(n);
    for (int i = 0; i < n ; i++) cin >> levelOrder[i];

    TreeNode* root = constructBinaryTree(levelOrder);
    dfs(root);
    cout << result << endl;

    return 0;
}

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

# Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

public class Main {
    public static int result = 0;

    public static TreeNode constructBinaryTree(List<String> levelOrder) {
        if (levelOrder.isEmpty()) return null;

        TreeNode root = new TreeNode(Integer.parseInt(levelOrder.get(0)));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;

        while (!queue.isEmpty() && i < levelOrder.size()) {
            TreeNode current = queue.poll();

            if (i < levelOrder.size() && !levelOrder.get(i).equals("null")) {
                current.left = new TreeNode(Integer.parseInt(levelOrder.get(i)));
                queue.add(current.left);
            }
            i++;

            if (i < levelOrder.size() && !levelOrder.get(i).equals("null")) {
                current.right = new TreeNode(Integer.parseInt(levelOrder.get(i)));
                queue.add(current.right);
            }
            i++;
        }

        return root;
    }

    public static int dfs(TreeNode node) {
        if (node == null) return 0;
        int leftPath = dfs(node.left);
        int rightPath = dfs(node.right);

        int leftNum = 0, rightNum = 0;
        if (node.left != null && node.left.val == node.val) {
            leftNum = leftPath + 1;
        }
        if (node.right != null && node.right.val == node.val) {
            rightNum = rightPath + 1;
        }
        result = Math.max(result, leftNum + rightNum);
        return Math.max(leftNum, rightNum);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();  // consume the newline character
        List<String> levelOrder = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            levelOrder.add(sc.next());
        }
        TreeNode root = constructBinaryTree(levelOrder);
        dfs(root);
        System.out.println(result);
        sc.close();
    }
}

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

# python

from typing import List, Optional
from collections import deque
import sys

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

def construct_binary_tree(level_order: List[str]) -> Optional[TreeNode]:
    if not level_order:
        return None

    root = TreeNode(int(level_order[0]))
    queue = deque([root])
    i = 1

    while queue and i < len(level_order):
        current = queue.popleft()

        if i < len(level_order) and level_order[i] != "null":
            current.left = TreeNode(int(level_order[i]))
            queue.append(current.left)
        i += 1

        if i < len(level_order) and level_order[i] != "null":
            current.right = TreeNode(int(level_order[i]))
            queue.append(current.right)
        i += 1

    return root

result = 0

def dfs(node: Optional[TreeNode]) -> int:
    global result
    if node is None:
        return 0

    left_path = dfs(node.left)
    right_path = dfs(node.right)

    left_num = right_num = 0
    if node.left is not None and node.left.val == node.val:
        left_num = left_path + 1
    if node.right is not None and node.right.val == node.val:
        right_num = right_path + 1

    result = max(result, left_num + right_num)
    return max(left_num, right_num)

if __name__ == "__main__":
    input = sys.stdin.read
    data = input().strip().split()

    n = int(data[0])
    level_order = data[1:]

    root = construct_binary_tree(level_order)
    dfs(root)
    print(result)

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
58
59
60
61
62
63
64