leetcode 124. Binary Tree Maximum Path Sum 、543. Diameter of Binary Tree(直径)

124. Binary Tree Maximum Path Sum

https://www.cnblogs.com/grandyang/p/4280120.html

如果你要计算加上当前节点的最大path和，这个节点的左右子树必定是纯左右树(即没有拐点)，

用另一个参数保留整个二叉树的最大path和，然后计算每一个以当前节点为拐点的路径和并且不断更新整个二叉树的最大值

函数的返回值是纯左右子树的最大path，没有拐点

这个题目给root定位为非空，所以直接这样写可以。如果root为空，这样写就会返回INT_MIN这个值，解决办法就是在最开始加是否为空的判断。

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        maxpath(root,res);
        return res;
    }
    int maxpath(TreeNode* root,int &res){
        if(root == NULL)
            return 0;
        int left = max(0,maxpath(root->left,res));
        int right = max(0,maxpath(root->right,res));
        res = max(res,left + right + root->val);
        return max(left,right) + root->val;
    }
};

 注意：分的过程中，left、right的迭代都使用了同一个res作为参数传入，而自己实现的平衡二叉树使用了两个不同的参数。

　　    首先使用同一个是没有错误的，因为这个题，无论左右子树其实都保存的同一个最大值，无需分别对待。而平衡二叉树中左右子树的深度不一样，使用不同的参数也合理

自己写的一个版本：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int sum = INT_MIN;
        maxPathSum(root,sum);
        return sum;
    }
    int maxPathSum(TreeNode* root,int& sum){
        if(!root)
            return 0;
        int sum1 = sum,sum2 = sum;
        int left = max(0,maxPathSum(root->left,sum1));
        int right = max(0,maxPathSum(root->right,sum2));
        sum = max(left + right + root->val,max(sum1,sum2));
        return max(left,right) + root->val;
    }
};

必须注意与0比较，因为有负数的情况，可以不加left、right。

必须是INT_MIN，这样可以排除一个负数做根节点，没有左右子树的情况，必须[-3]

这种写法是会超时的，因为你递归了两次；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        if(!root)
            return -1;
        int maxSum = INT_MIN;
        maxPathSum(root,maxSum);
        return maxSum;
    }
    int maxPathSum(TreeNode* root,int& maxSum){
        if(!root)
            return 0;
        int left = maxPathSum(root->left,maxSum) > 0 ? maxPathSum(root->left,maxSum) : 0;
        int right = maxPathSum(root->right,maxSum) > 0 ? maxPathSum(root->right,maxSum) : 0;
        maxSum = max(maxSum,left + right + root->val);
        return root->val + max(left,right);
    }
};

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        int depth = 0;
        return Balanced(root,depth);
    }
    bool Balanced(TreeNode* root,int& depth){
        if(root == NULL){
            depth = 0;
            return true;
        }
        int left,right;
        if(Balanced(root->left,left) && Balanced(root->right,right)){
            int gap = left - right;
            if(gap <= 1 && gap >= -1){
                depth = left > right ? left + 1 : right + 1;
                return true;
            }
        }
        return false;
    }
};

124题和543题很相似，因为两者实质上都是判断拐点的问题，用返回值表示纯拐点的值，用res值记录最大值就可以。

两者不同的是，124需要加每个节点的值，543是算直径。

543. Diameter of Binary Tree(直径)

https://blog.csdn.net/laputafallen/article/details/80147877

首先明确这里的直径是相当于连接的线的个数，比如4个节点，那直径就是3。所以对于一个节点，他的直径就是他的左右节点的高度和。但是最长的直径不一定是经过根节点的，比如题目中[1,2,3,4,5]这种情况，你如果把4、5都拉长一个，那最长的那个直径对应的根节点应该是2。所以每次求左右子树的高度，然后再跟最大的直径比就好了。

注意：直径是连线的个数，不是节点的个数，比如1、2、3、4连起来，有4个节点，但是实际上只有3条线在连，直径为3，不为4

原始代码：

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        diameterCore(root);
        return diameter;
    }
    int diameterCore(TreeNode* root){
        if(root == NULL)
            return 0;
        int left = diameterCore(root->left);
        int right = diameterCore(root->right);
        diameter = max(diameter,left + right);
        return left > right ? left + 1 : right + 1;
    }
    int diameter = 0;
};

因为两个题很相似，所以也可以写成124题这样的形式：

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