题目

https://leetcode.com/problems/longest-univalue-path/

题解：树形 dp 套路

实现1：带有 Info 类的树形 dp

/** * 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 Info {
    int depth;
    int val;
}

class Solution {
    int result;

    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return result;
    }

    public Info dfs(TreeNode node) {
        if (node == null) return null;

        Info leftInfo = dfs(node.left);
        Info rightInfo = dfs(node.right);

        Info info = new Info();
        info.depth = 0;
        info.val = node.val;

        int length = 0;
        if (leftInfo != null && leftInfo.val == node.val) {
            length += leftInfo.depth + 1;
            info.depth = leftInfo.depth + 1;
        }
        if (rightInfo != null && rightInfo.val == node.val) {
            length += rightInfo.depth + 1;
            info.depth = Math.max(info.depth, rightInfo.depth + 1);
        }
        result = Math.max(result, length);
        return info;
    }
}

实现2：不带 Info 类的树形 dp

后来发现，Info.val 始终是 node.val，所以根本不用存 Info.val 字段，直接用 node.left.val, node.right.val 代替就可以。

然后，Info 类就只剩下一个字段了，一个字段还有啥用？直接用裸的 int 了。

于是，对上面的代码进行了改造。改造后：

/** * 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 {
    int result;

    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return result;
    }

    public int dfs(TreeNode node) {
        if (node == null) return -1;

        int leftDepth = dfs(node.left);
        int rightDepth = dfs(node.right);

        int depth = 0;
        int length = 0;
        
        if (leftDepth != -1 && node.left.val == node.val) {
            length += leftDepth + 1;
            depth = leftDepth + 1;
        }
        if (rightDepth != -1 && node.right.val == node.val) {
            length += rightDepth + 1;
            depth = Math.max(depth, rightDepth + 1);
        }
        result = Math.max(result, length);
        return depth;
    }
}