1.思路
在树上做动态规划，在树上收集左树信息，收集右树信息，然后做逻辑处理，相当于是后序遍历，在遍历的过程中，记录了整棵树的节点信息，最后根据题意解题。
1.1 递归套路
- 假设以X节点为头，假设可以向X左树和X右树要任何信息
- 在上一步的假设下，假设以X为头节点的树，得到答案的可能性（关键）
- 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
- 把左树信息和右树信息求全集，即任何一棵子树都需要返回信息S
- 递归函数都返回S，每一棵子树都这么要求
- 写代码，在代码中考虑如何把左树的信息和右树的信息进行整合出整棵树的信息
1.2 时间复杂度
相当于对整个树，做后序遍历，时间复杂度O(n)
1.3 模版
/**
* 定义遍历过程中要记录的信息
*/
public class NodeInfo{
public Object info;//记录你需要的信息
public NodeInfo(Object info){
this.info = info;
}
}
/**
* 开始处理递归遍历处理
*/
public NodeInfo process(TreeNode treeNode){
//0.根据情况做badCase
if(treeNode == null){
//特殊标识
return new NodeInfo();
}
//1.收集信息
NodeInfo leftInfo = process(treeNode.left);
NodeInfo rightInfo = process(treeNode.right);
//2.分情况讨论，整合信息x
Object nodeInfo;
if(leftInfo != null && rightInfo != null){
//do something
//nodeInfo = ...
}
//3.打完收工
return new NodeInfo(nodeInfo);
}
/**
* 问题入口
* @param node
* @return
*/
public static int sulution(TreeNode node){
//1.简单判断
if(node == null){
return null;
}
//2.开始执行
NodeInfo nodeInfo = process(node);
//3.返回结果
return nodeInfo.info;
}
2. 实战题目
2.1 返回二叉树的的最大距离
任意两节点之间的距离最大，节点的之间的距离为1，且每个节点只能经过一次。
思路：
1.最大距离的可能性：
- p1. 和X头节点无关，左树的最大距离 就是最大距离
- p2. 和X头节点无关，右树的最大距离 就是最大距离
- p3. 和X有关，左树的高度 + 右树的高度 + 1（和自己x节点连起来，所以说是叫有关）
2.需要收集信息：
- 以任何节点作为root时的整棵树最大距离 maxDistance
- 以任何节点作为root时的整棵树的高度 height
3.逻辑
- 空节点：maxDistance = 0; height = 0
- height = Math.max(左树.height, 右树.height) + 1;
- maxDistance = Math.max(p1,p2,p3)
public static int maxDistance(TreeNode node){
return process(node).maxDistance;
}
public static PathInfo process(TreeNode treeNode){
if(treeNode == null){
return new PathInfo(0,0);
}
//1.收集信息
PathInfo leftInfo = process(treeNode.left);
PathInfo rightInfo = process(treeNode.right);
//2.整合信息
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
//比较3中可能性，得到maxDistance
int p1 = leftInfo.maxDistance;
int p2 = rightInfo.maxDistance;
int p3 = leftInfo.height + rightInfo.height + 1;
int maxDistance = Math.max(p1, Math.max(p2, p3));
//3.收工，返回
return new PathInfo(maxDistance, height);
}
public static class PathInfo{
public int maxDistance;
public int height;
public PathInfo(int maxDistance, int height){
this.maxDistance = maxDistance;
this.height = height;
}
}
2.2 返回二叉树的的最大距离
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
思路：
1.可能性
由题目知必然和和头节点有关系，
- p1: 头节点 左右都为null，单独作为路径
- p2: 头节点 + 左边节点，作为路径
- P3: 头节点 + 右边节点，作为路径
最后for: 左树上的所有路径集合 + 头节点value + 右树上的所有路径集合 = target
2.需要收集的信息
- 所有路径集合（必带头节点的路径）
- 路径包括：路径合，路径上的各个节点值 也需要记录
3.逻辑
- 空节点返回null
- 路径集合：List
- 路径和：sums = node.val + 左树.sums (or 右树.sums)
- 路径节点集合：pathList = node.value + 左树.pathList (or 右树.pathList)
public List<List<Integer>> pathTarget(TreeNode root, int target) {
//1.简单判断
List<List<Integer>> result = new ArrayList<>();
if(root == null){
return result;
}
if(root.left == null && root.right == null && root.val == target){
result.add(Arrays.asList(root.val));
return result;
}
//2.开始执行
NodePathInfo rootPathInfo = process(root);
//3.返回结果，遍历path找符合的解
List<Path> rootPathList = rootPathInfo.pathList;
for (Path path : rootPathList) {
if(target == path.sums){
result.add(path.pathValue);
}
}
return result;
}
public NodePathInfo process(TreeNode node){
if(node == null){
return null;
}
//1.收集信息
NodePathInfo leftInfo = process(node.left);
NodePathInfo rightInfo = process(node.right);
//2.整合信息
List<Path> pathList = new ArrayList<>();
//p1 头节点 单独作为路径
if(leftInfo == null && rightInfo == null){
pathList.add(new Path(node.val, Arrays.asList(node.val)));
}
//p2 头节点 + 左边节点 作为路径
if(leftInfo!=null){
List<Path> leftPathList = leftInfo.pathList;
//遍历左树，加上头节点，重新生成新的path
for (Path path : leftPathList) {
List<Integer> newPathList = new ArrayList<>();
newPathList.add(node.val);
newPathList.addAll(path.pathValue);
pathList.add(new Path(node.val + path.sums, newPathList));
}
}
//p3 头节点 + 右边节点 作为路径
if(rightInfo!=null){
List<Path> rightPathList = rightInfo.pathList;
//遍历右树树，加上头节点，重新生成新的path
for (Path path : rightPathList) {
List<Integer> newPathList = new ArrayList<>();
newPathList.add(node.val);
newPathList.addAll(path.pathValue);
pathList.add(new Path(node.val + path.sums, newPathList));
}
}
//3.打完收工
return new NodePathInfo(pathList);
}
public class NodePathInfo{
private List<Path> pathList;
public NodePathInfo(List<Path> pathList){
this.pathList = pathList;
}
}
public class Path{
private Integer sums;
private List<Integer> pathValue;
public Path(Integer sums, List<Integer> pathValue){
this.sums = sums;
this.pathValue = pathValue;
}
}
