本文共 1668 字，大约阅读时间需要 5 分钟。

Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y - sum of nodes in the common path from root to first common ancestor of the Nodes X and Y

---------------------------------------------------------------------------------------------

My idea: 
1. Traverse the tree. For each node compute: 
R - the path from the root (i.e. the sum of all nodes from the root to this node) 
Q - the max path to a leaf 
This me be done recursively in O(N) space and time. 
2. Traverse the tree again maximizing Q of left subtree + Q of right subtree - R.

class TreeNode { public:  int val, toRoot, maxPath;  TreeNode *left, *right;  TreeNode(int val = 0):val(val), left(NULL), right(NULL) {}};class Solution { public:  int findMaxPath(TreeNode* root) {    if (root->left == NULL && root->right == NULL)      return root->val;        int l = INT_MIN, r = INT_MIN;    if (root->left) {      root->left->toRoot = root->toRoot + root->val;      root->left->maxPath = l = findMaxPath(root->left);    }    if (root->right) {      root->right->toRoot = root->toRoot + root->val;      root->right->maxPath = r = findMaxPath(root->right);        }    return root->val + max(l, r);  }  void findMaxSum(TreeNode* root) {    if (root == NULL)      return;    if (root->toRoot + root->maxPath < res)      res = root->toRoot + root->maxPath;    findMaxSum(root->left);    findMaxSum(root->right);   }  int findRes(TreeNode* root) {    int res = INT_MAX;    if (root == NULL)      return 0;    root->toRoot = 0;    root->maxPath = findMaxPath(root);    return findMaxSum(root);  }}

转载地址：http://bwboi.baihongyu.com/