[leetcode_124]Binary Tree Maximum Path Sum

求出二叉树中的距离和。
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,

Return 6.

递归寻找所有情况，针对每个点是：max(只取该点，左子树贡献的最大值+该点，左子树贡献的最大值+该点+右子树贡献的最大值，该点+右子树的最大值)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


class Solution {
public:
    int result;
    int maxPathSum(TreeNode *root) {
        result = 0x80000001;
        if(root != NULL) {
            queryNodes(root);
        }
        return result;
    }
private:
    void queryNodes(TreeNode *node) {
        if(node->left == NULL && node->right == NULL) {
            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;
        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;
    }
};