二叉树后序遍历的巧妙用法

当要解决的问题是先收集到左右子树的信息再统一在当前节点进行处理时，典型的后序遍历。
构思的难点在于：子节点要向父节点返回什么信息?这题要想到子节点要返回的，是从当前节点出发，能够向下延伸与其值相同的最大深度。那么返回值分两种情况：1)当前节点与其左右孩子节点的值都不相等，则深度为0
2)左右深度的最大值+1. （孩子节点对父节点的深度贡献只能取其中最大的，不能是相加，因为子节点返回的不能是分岔的路径。在父节点处时，更新全局变量维护的最长路径值。）
参考代码：

class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        int ans = 0;
        helper(root,ans);
        return ans;
    }
    int helper(TreeNode* root, int& ans){
        if(!root) return 0;
        int l = helper(root->left,ans);
        int r = helper(root->right,ans);
        int samel = 0, samer = 0;
        if(root->left&&root->val==root->left->val)
            samel = l + 1;
        if(root->right&&root->right->val==root->val)
            samer = r + 1;
    // 更新全局最大值
        ans = max(ans,samel+samer);
         // 返回对父节点的贡献的最大深度
        return max(samer,samel);
    }
};

相似题目

思路一样，子节点贡献给父节点的最大路径和只能来自于max(当前节点本身，max(当前节点值加左子树和，当前节点值加右子树和))。同样地,在父节点处更新全局变量维护的最大路径和。
参考代码：

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int ans = INT_MIN;
        helper(root,ans);
        return ans;

    }
    int helper(TreeNode* root, int& ans){
        if(!root) return 0;
        int sumr = helper(root->left,ans);
        int suml = helper(root->right,ans);
        // 将左右子树收集到的情况汇总到当前节点处理
        // 最大路径和的可能来源：当前节点，当前节点+左子树，当前节点+右子树，当前节点+左子树+右子树 
        ans = max(ans,max(max(root->val,max(root->val+suml,root->val+sumr)),root->val+sumr+suml));
        // 返回子节点对父节点的最大贡献
        return max(root->val,max(root->val+suml,root->val+sumr));
    }
};

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;
        helper(root,ans);
        return ans;
    }
    int helper(TreeNode* root,int& ans){
        if(!root) return 0;
        int left = helper(root->left,ans) + 1;
        int right = helper(root->right,ans) + 1;
        ans = max(ans,left+right-2);
        return max(left,right);
    }
};