问题描述：给定一个非空二叉树，返回其最大路径和。路径被定义为一条从树中任意节点出发，达到任意节点的序列，该路径至少包含一个节点，且不一定经过根节点。
二叉树动态规划：定义一个类，其中一个元素是TreeNode，其中一个元素是从当前元素往下走的最大值maxValue。初始化时找到所有的叶子结点，并是所有叶子节点的值为其TreeNode.val。在遍历的过程中，如果左节点和右节点的值均小于0，则其值等于其本身节点的值，否则取大一些的值与该节点本身的值相加，作为该节点的最大路劲和。
class newTreeNode
{
public:
TreeNode originTreeNode;
int maxValue;
TreeNode left;
TreeNode right;
newTreeNode(){originTreeNode=null;left=null;right=null;}
}
newTreeNode newRoot;
int maxValue;
public void gennerateNewTreeNode(TreeNode root,newTreeNode parent,Boolean leftOrRight)
{
if(root==null){return;}
newTreeNode newNode=new newTreeNode();
newNode.originTreeNode=root;
if(parent!=null)
{
if(leftOrRight)
{
parent.left=newNode;
gennerateNewTreeNode(root.left,newNode,true);
gennerateNewTreeNode(root.right,newNode,false);
}else
{
parent.right=newNode;
gennerateNewTreeNode(root.left,newNode,true);
gennerateNewTreeNode(root.right,newNode,false);
}
}else
{
newRoot=newNode;
gennerateNewTreeNode(root.left,newRoot,true);
gennerateNewTreeNode(root.right,newRoot,false);
}
}
public int initialNewTreeNode(newTreeNode root)
{
if(root==null){return 0;}
root.maxValue=Math.max(Math.max(root.originTreeNode.val,root.originTreeNode.val+initialNewTreeNode(root.left)),root.originTreeNode.val+initialNewTreeNode(root.right));
return root.maxValue;
}
public void maxSum(newTreeNode root)
{
if(root==null){return;}
maxValue=Math.max(root.maxValue,maxValue);
maxSum(root.left);
maxSum(root.right);
}
public int MaxSum(TreeNode root)
{
gennerateNewTreeNode(root,null,true);
initialNewTreeNode(newRoot);
maxSum(newRoot);
return maxValue;
}