【labuladong】二叉树/递归的框架思维（纲领篇）
培养框架思维： 去掉detail的easy 题；算法基于easy的ds，思维低层逻辑
二叉树 是 backtrack(dfs), dp的同类root:
traverse 二叉树， 分解问题计算出答案
（预习：先学array等小而妙的算法,linkedlist, binary tree, dfs, dp)
- quick sort: 前序遍历：mid, left, right
void sort(int[] nums, int lo, int hi) {
// pre order place:
通过交换元素构建分界点 P pre序遍历；
int p = partition (nums, lo, hi); //preorder 位置
sort (nums, lo, p - 1) traverse (root left)
sort (nums, p + 1, hi) traverse (root right)
merget sort的代码框架如下：
definition： sort nums [lo..hi j
void sort(int[] nums, int lo, int hi)
int mid (lo + hi) / 2
// sort (nums, lo, mid)
sort(nums, lo, mid)
// sort nums [mid+1..hi]
sort(nums, mid + 1, hi)
// post order place:
// merge nums[lo..mid]and nums[mid+1..hi]
merge (nums, lo, mid, hi)
}
归并排序： 后序遍历；
void traverse (TreeNode root)
traverse (root left)
traverse (root right)
//后序位置 curr node;
summary: 复杂的算法都是由简单的构成
---------------
二叉树解题的思维模式分两类：
1、是否可以通过traverse一遍二叉树得到客察？如果可以，用一个 traverse 函数配合外部变量来实现。这叫「遍历」的思维模式。 diameter，max path sum/length
2、是否可以定义一个recursion function，通过子问题 （子树）的答案推导出原问题的答案？如果可以，写出这个递recursion function的definition，并充分利用这个recursion function的返回值，这叫「分解问题」的思维楼式。
return recursion function(XX) || recursion function(YY)
无论使用哪种思维模式。你都需要思考：
如果单独抽出一个二叉树node，它需要做什么事情？需要在什么时候（前/中/后序位量）做？其他的节点不用你care，递归函数会帮你在所有节点上执行same execution。
(do what in curr node)
从最简单的问题中提炼出所有二叉树题目的共性，并将二叉树中蕴含的思维进行升华，反手用到 动态規划，backtrack， 分治算法，graph 中去．这也是我一直强调框架思维的原因。希望你在学习了上述高级算法后，也能回头再来看看本文，会对它们有更深刻的认识。
说了这么多基础的，就是要帮你对二叉树建立正确的认识，然后你会发现：
二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码logic，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。
你也可以看到，固论牌法基础 把二叉树的追历框架扩展到了圈，并以追历为基
---------
recursion 根据定义用语言表示出来：
---复习：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。
3、无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。
这两个问题的根本区别在于：一个节点在第几层，你从根节点遍历过来的过程就能顺带记录，用递归函数的参数就能传递下去；而以一个节点为根的整棵子树有多少个节点，你需要遍历完子树之后才能数清楚，然后通过递归函数的返回值拿到答案。
结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。
那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。
---------搞懂了我之前觉得很馄饨的recursion
我求整棵树中的最长「直径」，那直截了当的思路就是遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度算出每个节点的「直径」，最后把所有「直径」求个最大值即可。
class Solution {
// 记录最大直径的长度
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxDiameter;
}
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置，顺便计算最大直径
int myDiameter = leftMax + rightMax;
maxDiameter = Math.max(maxDiameter, myDiameter);
return 1 + Math.max(leftMax, rightMax);
}
照应一下前文：遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。
366:
class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> output = new ArrayList<>();
while(root != null){//.left != null && root.right != null) {
List<Integer> res = new ArrayList<>();//
root = helper(root,res);//
output.add(res);
}
return output;
}
private TreeNode helper(TreeNode root, List<Integer> res) {
if(root == null){
return null;
}
if(root.left == null && root.right == null) {
res.add(root.val);
return null;
}
root.left = helper(root.left, res);//
root.right = helper(root.right, res);//
return root;//res;//wrong
}
}
public List<List<Integer>> findLeaves(TreeNode root) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
int treeHeight = findHeight(root, map);
List<List<Integer>> res = new ArrayList<>();
for (int i = 1; i <= treeHeight; i++) {
res.add(map.get(i));
}
return res;
}
public int findHeight(TreeNode root, HashMap<Integer, ArrayList<Integer>> map) {
if (root == null) {
return 0;
}
int leftHeight = findHeight(root.left, map);
int rightHeight = findHeight(root.right, map);
int currHeight = Math.max(leftHeight, rightHeight) + 1;
if (map.get(currHeight) == null) {
map.put(currHeight, new ArrayList<Integer>());
}
map.get(currHeight).add(root.val);
return currHeight;
}
}
