方法思路

1. 这个问题要求找出二叉树中最长的同值路径长度
2. 同值路径是指树中所有节点值相同的一条路径，可以经过也可以不经过根节点
3. 我们可以使用递归的方式来解决这个问题：
   • 对于每个节点，计算以该节点为起点，向左和向右延伸的最长同值路径长度
   • 然后更新全局最大值，考虑将左右路径连接起来形成的路径长度
4. 具体步骤：
   • 首先根据输入构建二叉树
   • 定义一个递归函数，计算从当前节点出发的最长同值路径长度
   • 在递归过程中更新全局最大值
   • 返回全局最大值作为结果

代码实现

Java

import java.util.*;

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

public class Main {
    // 全局变量，记录最长同值路径长度
    private static int maxLength = 0;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
        
        String[] nodes = scanner.nextLine().split(" ");
        
        // 构建二叉树
        TreeNode root = buildTree(nodes);
        
        // 计算最长同值路径长度
        longestUnivaluePath(root);
        
        System.out.println(maxLength);
    }
    
    private static int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // 递归计算左右子树的最长同值路径
        int leftLength = dfs(node.left);
        int rightLength = dfs(node.right);
        
        // 初始化左右延伸长度为0
        int leftArrow = 0, rightArrow = 0;
        
        // 如果左子节点存在且值与当前节点相同，更新左延伸长度
        if (node.left != null && node.left.val == node.val) {
            leftArrow = leftLength + 1;
        }
        
        // 如果右子节点存在且值与当前节点相同，更新右延伸长度
        if (node.right != null && node.right.val == node.val) {
            rightArrow = rightLength + 1;
        }
        
        // 更新全局最大值，考虑左右路径连接起来的情况
        maxLength = Math.max(maxLength, leftArrow + rightArrow);
        
        // 返回从当前节点出发的最长同值路径长度
        return Math.max(leftArrow, rightArrow);
    }
    
    private static int longestUnivaluePath(TreeNode root) {
        maxLength = 0;
        dfs(root);
        return maxLength;
    }
    
    private static TreeNode buildTree(String[] nodes) {
        if (nodes == null || nodes.length == 0 || nodes[0].equals("null")) {
            return null;
        }
        
        // 创建根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        
        // 使用队列进行层序构建
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        int i = 1;
        while (!queue.isEmpty() && i < nodes.length) {
            TreeNode node = queue.poll();
            
            // 构建左子节点
            if (i < nodes.length && !nodes[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(nodes[i]));
                queue.offer(node.left);
            }
            i++;
            
            // 构建右子节点
            if (i < nodes.length && !nodes[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(nodes[i]));
                queue.offer(node.right);
            }
            i++;
        }
        
        return root;
    }
}

Python

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

def longest_univalue_path(root):
    # 全局变量，记录最长同值路径长度
    max_length = [0]
    
    def dfs(node):
        if not node:
            return 0
        
        # 递归计算左右子树的最长同值路径
        left_length = dfs(node.left)
        right_length = dfs(node.right)
        
        # 初始化左右延伸长度为0
        left_arrow = right_arrow = 0
        
        # 如果左子节点存在且值与当前节点相同，更新左延伸长度
        if node.left and node.left.val == node.val:
            left_arrow = left_length + 1
        
        # 如果右子节点存在且值与当前节点相同，更新右延伸长度
        if node.right and node.right.val == node.val:
            right_arrow = right_length + 1
        
        # 更新全局最大值，考虑左右路径连接起来的情况
        max_length[0] = max(max_length[0], left_arrow + right_arrow)
        
        # 返回从当前节点出发的最长同值路径长度
        return max(left_arrow, right_arrow)
    
    dfs(root)
    return max_length[0]

def build_tree(nodes):
    if not nodes:
        return None
    
    # 创建根节点
    root = TreeNode(int(nodes[0])) if nodes[0] != "null" else None
    if not root:
        return None
    
    # 使用队列进行层序构建
    queue = [root]
    i = 1
    while queue and i < len(nodes):
        node = queue.pop(0)
        
        # 构建左子节点
        if i < len(nodes) and nodes[i] != "null":
            node.left = TreeNode(int(nodes[i]))
            queue.append(node.left)
        i += 1
        
        # 构建右子节点
        if i < len(nodes) and nodes[i] != "null":
            node.right = TreeNode(int(nodes[i]))
            queue.append(node.right)
        i += 1
    
    return root

# 读取输入
n = int(input())
nodes = input().split()

# 构建二叉树
root = build_tree(nodes)

# 计算最长同值路径长度
result = longest_univalue_path(root)
print(result)

C++

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

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

// 全局变量，记录最长同值路径长度
int maxLength = 0;

// 递归函数，计算从当前节点出发的最长同值路径长度
int dfs(TreeNode* node) {
    if (!node) {
        return 0;
    }
    
    // 递归计算左右子树的最长同值路径
    int leftLength = dfs(node->left);
    int rightLength = dfs(node->right);
    
    // 初始化左右延伸长度为0
    int leftArrow = 0, rightArrow = 0;
    
    // 如果左子节点存在且值与当前节点相同，更新左延伸长度
    if (node->left && node->left->val == node->val) {
        leftArrow = leftLength + 1;
    }
    
    // 如果右子节点存在且值与当前节点相同，更新右延伸长度
    if (node->right && node->right->val == node->val) {
        rightArrow = rightLength + 1;
    }
    
    // 更新全局最大值，考虑左右路径连接起来的情况
    maxLength = max(maxLength, leftArrow + rightArrow);
    
    // 返回从当前节点出发的最长同值路径长度
    return max(leftArrow, rightArrow);
}

int longestUnivaluePath(TreeNode* root) {
    maxLength = 0;
    dfs(root);
    return maxLength;
}

// 构建二叉树
TreeNode* buildTree(vector<string>& nodes) {
    if (nodes.empty() || nodes[0] == "null") {
        return nullptr;
    }
    
    // 创建根节点
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    
    // 使用队列进行层序构建
    queue<TreeNode*> q;
    q.push(root);
    
    int i = 1;
    while (!q.empty() && i < nodes.size()) {
        TreeNode* node = q.front();
        q.pop();
        
        // 构建左子节点
        if (i < nodes.size() && nodes[i] != "null") {
            node->left = new TreeNode(stoi(nodes[i]));
            q.push(node->left);
        }
        i++;
        
        // 构建右子节点
        if (i < nodes.size() && nodes[i] != "null") {
            node->right = new TreeNode(stoi(nodes[i]));
            q.push(node->right);
        }
        i++;
    }
    
    return root;
}

int main() {
    int n;
    cin >> n;
    
    vector<string> nodes(n);
    for (int i = 0; i < n; i++) {
        cin >> nodes[i];
    }
    
    // 构建二叉树
    TreeNode* root = buildTree(nodes);
    
    // 计算最长同值路径长度
    int result = longestUnivaluePath(root);
    cout << result << endl;
    
    return 0;
}