题目描述

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

   1
  / \
 2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

题解1：

二叉树 abc，a 是根结点（递归中的 root），bc 是左右子结点（代表其递归后的最优解）。
最大的路径，可能的路径情况：

    a
   / \
  b   c

(1) b + a + c
(2) b + a + (a的父亲节点)
(3) c + a + (a的父亲节点)

//dfs返回左分支或者右分支的最大值(不包括第1种情况)
int dfs(TreeNode* root, int val)
{
    if(root==NULL)
        return 0;    

    int left = dfs(root->left,val);
    int right = dfs(root->right,val);

    //第1种情况
    int num_one = root->val+max(0,left)+max(0,right);

    //第2或者3情况
    int num_two = root->val+max(0,max(left,right));  

    //保存可能的结果的最大值    
    val = max(val,max(num_one,num_two));

    return num_two;
}

题解2：

可以记录每个节点的直系父亲节点，然后将p节点的所有父节点加入一个集合S中，然后对q进行查询他的父节点是否在集合S中，当在时，则直接返回即可。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    //建立子节点与父节点的映射关系
    map<TreeNode*, TreeNode*> m;
    //遍历树节点
    queue<TreeNode* > que;
    que.push(root);
    while(!que.empty())
    {
        TreeNode* tmp = que.front();
        que.pop();
        if(tmp->left!=NULL)
        {
            m[tmp->left] = tmp;
            que.push(tmp->left);
        }
        if(tmp->right!=NULL)
        {
            m[tmp->right] = tmp;
            que.push(tmp->right);
        }
    }

    //p节点所有父亲节点集合
    set<TreeNode* > S;
    S.insert(p);
    while(m.find(p)!=m.end())
    {
        S.insert(m[p]);
        p = m[p];
    }

    //看q的父亲节点是否在集合S中
    if(s1.find(q)!=S.end())
        return q;      
    while(m.find(q)!=m.end())
    {
        if(S.find(m[q])!=S.end())
            return m[q];
        q = m[q];
    }

    return NULL;
}