Daily LeetCode – day0035 0687. Longest Univalue Path

// 0687. Longest Univalue Path
class Solution {
    public int longestUnivaluePath(TreeNode root) {
        int[] ans = new int[]{0};
        if (root == null) return 0;
        dfs(root, ans);
        return ans[0];
    }

    int dfs(TreeNode root, int[] ans) {
        if (root.left == null && root.right == null) return 1;
        int left = 0;
        int right = 0;
        if (root.left != null) {
            left = dfs(root.left, ans);
            if (root.left.val != root.val) left = 0;
        }
        if (root.right != null) {
            right = dfs(root.right, ans);
            if (root.right.val != root.val) right = 0;
        }
        int selfMax = left + right;
        if (selfMax > ans[0]) ans[0] = selfMax;
        if (left > right) return left + 1;
        return right + 1;
    }
}

学习笔记：
今天这道题目之前教学过，这道二叉树题有点像动态规划，需要从下往上状态转移，但由于存储方式是二叉树，所以还是应该用回溯算法，不断递归下去回溯上来。