面试题6——二叉树的最大路径和

扩展：问题4）路径可以从任何结点出发，但必须到叶节点，返回最大路径和

重要技巧：

• 二叉树的递归套路——平衡二叉树
• 二叉树的递归套路——二叉树的最大距离
• 二叉树的递归套路——最大二叉搜索子树大小
• 二叉树的递归套路——派对的最大快乐值
• 二叉树的递归套路——满二叉树
• 二叉树的递归套路——搜索二叉树
• 二叉树的递归套路——最大二叉搜索子树头结点
• 二叉树的递归套路——完全二叉树
• 二叉树的递归套路——最低公共祖先

package com.harrison.class01;

public class Code06_MaxSumInTree {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
			value = v;
		}
	}

	public static int maxSum = Integer.MIN_VALUE;

	// 问题1，方法一（不用二叉树的递归套路求解）：
	public static int maxSum11(Node head) {
		maxSum = Integer.MIN_VALUE;
		process11(head, 0);// 头结点的路径和为0
		return maxSum;
	}

	// 之前的路径和为pre
	public static void process11(Node x, int pre) {
		// 只有到叶结点的时候才跟maxSum结算
		if (x.left == null && x.right == null) {
			maxSum = Math.max(maxSum, pre + x.value);
		}
		if (x.left != null) {
			process11(x.left, pre + x.value);
		}
		if (x.right != null) {
			process11(x.right, pre + x.value);
		}
	}

	// 问题1，方法二（用二叉树的递归套路求解）：
	// 因为要的信息就是结点的值，所以不用单独封装信息体
	public static int maxSum12(Node head) {
		if (head == null) {
			return 0;
		}
		return process12(head);
	}

	// x为头的整棵树上，最大路径和是多少，返回
	// 路径要求，一定要从x出发，到达叶结点，算作一个路径
	// x并不一定是整棵树的头结点，但一定是每颗子树的头结点
	public static int process12(Node x) {
		if (x.left == null && x.right == null) {
			return x.value;
		}
		int next = Integer.MIN_VALUE;
		if (x.left != null) {
			next = process12(x.left);
		}
		if (x.right != null) {
			next = Math.max(next, process12(x.right));
		}
		return x.value + next;
	}

	// 问题2，用二叉树的递归套路
	public static int maxSum2(Node head) {
		if (head == null) {
			return 0;
		}
		return process2(head).allTreeMaxSum;
	}

	// 与x无关：1）左树上的整体最大路径和 1）右树上的整体最大路径和
	// 与x有关: 3）x自己 4）x往左树走 5）x往右树走
	public static class Info {
		public int allTreeMaxSum;
		public int fromHeadMaxSum;

		public Info(int a, int f) {
			allTreeMaxSum = a;
			fromHeadMaxSum = f;
		}
	}

	public static Info process2(Node x) {
		if (x == null) {
			return null;
		}
		Info leftInfo = process2(x.left);
		Info rightInfo = process2(x.right);
		int p1 = Integer.MIN_VALUE;
		if (leftInfo != null) {
			p1 = leftInfo.allTreeMaxSum;
		}
		int p2 = Integer.MIN_VALUE;
		if (rightInfo != null) {
			p2 = rightInfo.allTreeMaxSum;
		}
		int p3 = x.value;
		int p4 = Integer.MIN_VALUE;
		if (leftInfo != null) {
			p4 = leftInfo.fromHeadMaxSum;
		}
		int p5 = Integer.MIN_VALUE;
		if (rightInfo != null) {
			p5 = rightInfo.fromHeadMaxSum;
		}
		int allTreeMaxSum = Math.max(Math.max(p1, p2), Math.max(Math.max(p3, p4), p5));
		int formHeadMaxSum = Math.max(Math.max(p3, p4), p5);
		return new Info(allTreeMaxSum, formHeadMaxSum);
	}

	// 问题3，用二叉树的递归套路
	public static int maxSum3(Node head) {
		if (head == null) {
			return 0;
		}
		return process3(head).allTreeMaxSum;
	}

	// 与x无关：1）左树上的整体最大路径和 1）右树上的整体最大路径和
	// 与x有关: 3）x自己 4）x往左树走 5）x往右树走 6）x既往左，又往右
	// 第6)情况，并不是从x出发，只是经过x
	public static class Info3 {
		public int allTreeMaxSum;
		public int fromHeadMaxSum;

		public Info3(int a, int f) {
			allTreeMaxSum = a;
			fromHeadMaxSum = f;
		}
	}

	public static Info3 process3(Node x) {
		if (x == null) {
			return null;
		}
		Info3 leftInfo = process3(x.left);
		Info3 rightInfo = process3(x.right);
		int p1 = Integer.MIN_VALUE;
		if (leftInfo != null) {
			p1 = leftInfo.allTreeMaxSum;
		}
		int p2 = Integer.MIN_VALUE;
		if (rightInfo != null) {
			p2 = rightInfo.allTreeMaxSum;
		}
		int p3 = x.value;
		int p4 = Integer.MIN_VALUE;
		if (leftInfo != null) {
			p4 = leftInfo.fromHeadMaxSum;
		}
		int p5 = Integer.MIN_VALUE;
		if (rightInfo != null) {
			p5 = rightInfo.fromHeadMaxSum;
		}
		int p6 = Integer.MIN_VALUE;
		if (leftInfo != null && rightInfo != null) {
			p6 = x.value + leftInfo.fromHeadMaxSum + rightInfo.fromHeadMaxSum;
		}
		int allTreeMaxSum = Math.max(Math.max(p1, p2), Math.max(Math.max(Math.max(p3, p4), p5), p6));
		int formHeadMaxSum = Math.max(Math.max(p3, p4), p5);
		return new Info3(allTreeMaxSum, formHeadMaxSum);
	}
	
	public static int max=Integer.MIN_VALUE;
	
	// 扩展，问题4：可以从任何结点出发，但必须到叶节点，返回最大路径和
	public static int maxSum4(Node head) {
		if(head.left==null && head.right==null) {
			max=Math.max(max, head.value);
			return head.value;
		}
		int next=0;
		if(head.left!=null) {
			next=maxSum4(head.left);
		}
		if(head.right!=null) {
			next=Math.max(next, maxSum4(head.right));
		}
		int ans=head.value+next;
		max=Math.max(max, ans);
		return ans;
	}
	
	public static void main(String[] args) {
		Node head=new Node(4);
		head.left=new Node(1);
		head.left.right=new Node(5);
		head.right=new Node(-7);
		head.right.left=new Node(3);
		System.out.println(maxSum11(head));
		System.out.println(maxSum12(head));
		System.out.println(maxSum2(head));
		System.out.println(maxSum3(head));
		System.out.println(maxSum4(head));
	}
}