CareerCup Binary Tree the Maximum of 人

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);
  }
}

CareerCup Binary Tree the Maximum of 人,布布扣,bubuko.com

CareerCup Binary Tree the Maximum of 人

原文：http://blog.csdn.net/taoqick/article/details/20152983