LeetCode题解|687. Longest Univalue Path

题目链接：687. Longest Univalue Path

概述

给定一棵二叉树，找出树中有相同值的最长路径长度。

思路

使用DFS，找出每个节点的左右子树左右两边的最长路径值lr，如果当前节点与左(右)子树的节点值相等，则将当前节点的左(右)值定为左(右)子树lr中的最大值+1。

实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var longestUnivaluePath = function(root) {
    if(root == null){
        return 0;
    }
    var maxLength = 0;
    var dfs = function(node){
        if(node == null || (node.left == null && node.right == null)){
            return { left: 0, right: 0 };
        }
        const { left: ll, right: lr } = dfs(node.left);
        const { left: rl, right: rr } = dfs(node.right);
        
        var left = 0,
            right = 0;
        
        if(node.left != null && node.val == node.left.val){
            left = Math.max(ll, lr) + 1;
        }
        if(node.right != null && node.val == node.right.val){
            right = Math.max(rl, rr) + 1;
        }
        maxLength = Math.max(maxLength, left + right);
        return { left: left, right: right };
    }
    
    dfs(root);
    return maxLength;
};

题解合集