public int maxPathSum2(treeNode curRoot) {
		HashMap<treeNode, Integer> node_notRootMax = new HashMap<treeNode, Integer>();
		HashMap<treeNode, Integer> node_asRootMax = new HashMap<treeNode, Integer>();

		int maxPathNotRoot;
		int maxPathAsRoot;
		int curMax;
		int maxPathFinal = -10000;
		treeNode p = curRoot;

		if (p == null)
			return 0;

		// max for left tree
		while ((p = p.leftLeaf) != null) {
			maxPathNotRoot = maxPathNotRoot2(p, node_notRootMax);
			maxPathAsRoot = maxPathAsRoot2(p, node_notRootMax, node_asRootMax);

			curMax = maxPathNotRoot > maxPathAsRoot ? maxPathNotRoot
					: maxPathAsRoot;
			if (curMax > maxPathFinal) {
				maxPathFinal = curMax;
				this.highestPointForMaxPath = p;
			}
		}

		p = curRoot;
		// max for right tree
		while ((p = p.rightLeaf) != null) {
			maxPathNotRoot = maxPathNotRoot2(p, node_notRootMax);
			maxPathAsRoot = maxPathAsRoot2(p, node_notRootMax, node_asRootMax);

			curMax = maxPathNotRoot > maxPathAsRoot ? maxPathNotRoot
					: maxPathAsRoot;
			if (curMax > maxPathFinal) {
				maxPathFinal = curMax;
				this.highestPointForMaxPath = p;
			}
		}

		// max for root
		maxPathNotRoot = maxPathNotRoot2(curRoot, node_notRootMax);
		maxPathAsRoot = maxPathAsRoot2(curRoot, node_notRootMax, node_asRootMax);

		curMax = maxPathNotRoot > maxPathAsRoot ? maxPathNotRoot
				: maxPathAsRoot;
		if (curMax > maxPathFinal) {
			maxPathFinal = curMax;
			this.highestPointForMaxPath = curRoot;
		}

		System.out.println("Running time for method 2:"
				+ this.running_time_asRoot2 + "/" + this.running_time_NotRoot2);
		return maxPathFinal;
	}