public int maxPathSum3(treeNode root) {
        if(root == null) 
            return 0;
            
        if(root.leftLeaf == null && root.rightLeaf == null) 
            return root.value;

        PathMaxPair rootPair = maxPathPair(root);
		return rootPair.getMaxPathNoRoot();
	}