leetcode687最长同值路径

曾经终败给现在 2022-09-03 12:24 151阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
思路

1.  使用后序递归遍历二叉树
2.  找到左右子树的当前同值长度以及最大同值长度
3.  如果左子树存在且和根节点一致，那么当前左子树同值高度++，否则当前根节点左子树同值高度重置为0
4.  如果右子树存在且和根节点一致，那么当前右子树同值高度++，否则当前根节点右子树同值高度重置为0
5.  当前根节点的同值高度是max(左右子树同值高度)
6.  当前根节点最大同值长度是max(左右子树最大同值长度，左右子树同值高度之和)

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    
    #define max(a,b) ((a)>(b)?a:b)
    void longpath(struct TreeNode* root,int *h,int *max_h){ 
        if(root==NULL){ 
            *h = 0;
            *max_h = 0;
            return;
        }
        int hl = 0,hr=0,mhl=0,mhr=0;
        longpath(root->left,&hl,&mhl);
        longpath(root->right,&hr,&mhr);
        if(root->left!=NULL&&root->val==root->left->val)
                hl++;
        else hl = 0;//这个是与根节点相连的直接长度，断边了 max_h已经记录历史最大长度
        if(root->right!=NULL&&root->val==root->right->val)
                hr++;
        else hr = 0;
        *h = max(hr,hl);//左右子树最大值，已经考虑0了
        *max_h = max(*max_h,hr+hl);
        *max_h = max(*max_h,max(mhl,mhr));
        
    }
    int longestUnivaluePath(struct TreeNode* root){ 
        int h=0,max_h=0;
        longpath(root,&h,&max_h);
        return max_h;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/f56db823e4c1439a9eb74b6b8530b290.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/600774d981384534b1fa696c9b5c03dd.png