Binary Tree Maximum Path Sum II

Java

public class Solution {
    /**
     * @param root: the root of binary tree.
     * @return: An integer
     */
		public int maxPathSum2(TreeNode root) {
			if (root == null) return 0;
			int ans = Integer.MIN_VALUE;
			Queue<NewNode> queue = new LinkedList<>();
			queue.add(new NewNode(root, root.val)); //NewNode.sum 在这里初始化的？
			
			while (!queue.isEmpty()) {
				NewNode cur = queue.poll();
				if (cur.sum > ans) {
					ans = cur.sum;
				}
		if (cur.treeNode.left != null) queue.offer(new NewNode(cur.treeNode.left, cur.sum + cur.treeNode.left.val));
		if (cur.treeNode.left != null) queue.offer(new NewNode(cur.treeNode.right, cur.sum + cur.treeNode.right.val));
			}
			return ans;
}

public class NewNode {
		public TreeNode treeNode;
		public int sum;
		public NewNode(TreeNode treeNode, int sum) {
			this.treeNode = treeNode;
			this.sum = sum;
		}
	}
}