求出二叉树中的距离和。
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
递归寻找所有情况，针对每个点是：max(只取该点，左子树贡献的最大值+该点，左子树贡献的最大值+该点+右子树贡献的最大值，该点+右子树的最大值)。
class Solution {
public:
int result;
int maxPathSum(TreeNode *root) {
result = 0x80000001;
if(root != NULL) {
queryNodes(root);<br />
}
return result;
}
private:
void queryNodes(TreeNode * node) {
if(node ->left == NULL && node->right == NULL) {
//node->val = node->val>=0?node->val:0;
if(node -> val > result)result = node->val;
return;
}
if(node->left == NULL) {
queryNodes(node->right);
node->val = node->val + node->right->val >= node->val?node->val + node->right->val:node->val;
if(node -> val > result)result = node->val;
return;
}
if(node->right == NULL) {
queryNodes(node->left);
node->val = node->val + node->left->val >= node->val?node->val + node->left->val:node->val;
if(node -> val > result)result = node->val;
return;
}
queryNodes(node->right);
queryNodes(node->left);
if(node -> val > result)
result = node->val;
if(node -> val + node->left->val > result)
result = node -> val + node->left->val;
if(node -> val + node->right->val > result)
result = node -> val + node->right->val;
if(node -> val + node->right->val + node->left->val > result)
result = node -> val + node->right->val + node->left->val;<br />
int max = node->val + node->left->val >= node->val + node->right->val?node->val + node->left->val:node->val + node->right->val;
node->val = max >= node->val?max:node->val;<br />
}
};