【labuladong】二叉樹/遞歸的框架思維（綱領(lǐng)篇）
培養(yǎng)框架思維： 去掉detail的easy 題；算法基于easy的ds，思維低層邏輯
二叉樹 是 backtrack(dfs), dp的同類root:
traverse 二叉樹， 分解問題計算出答案
（預(yù)習(xí)：先學(xué)array等小而妙的算法,linkedlist, binary tree, dfs, dp)
- quick sort: 前序遍歷：mid, left, right
void sort(int[] nums, int lo, int hi) {
// pre order place:
通過交換元素構(gòu)建分界點(diǎn) 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: 復(fù)雜的算法都是由簡單的構(gòu)成
---------------
二叉樹解題的思維模式分兩類：
1、是否可以通過traverse一遍二叉樹得到客察？如果可以，用一個 traverse 函數(shù)配合外部變量來實(shí)現(xiàn)。這叫「遍歷」的思維模式。 diameter，max path sum/length
2、是否可以定義一個recursion function，通過子問題 （子樹）的答案推導(dǎo)出原問題的答案？如果可以，寫出這個遞recursion function的definition，并充分利用這個recursion function的返回值，這叫「分解問題」的思維樓式。
return recursion function(XX) || recursion function(YY)
無論使用哪種思維模式。你都需要思考：
如果單獨(dú)抽出一個二叉樹node，它需要做什么事情？需要在什么時候（前/中/后序位量）做？其他的節(jié)點(diǎn)不用你care，遞歸函數(shù)會幫你在所有節(jié)點(diǎn)上執(zhí)行same execution。
(do what in curr node)
從最簡單的問題中提煉出所有二叉樹題目的共性，并將二叉樹中蘊(yùn)含的思維進(jìn)行升華，反手用到 動態(tài)規(guī)劃，backtrack， 分治算法，graph 中去．這也是我一直強(qiáng)調(diào)框架思維的原因。希望你在學(xué)習(xí)了上述高級算法后，也能回頭再來看看本文，會對它們有更深刻的認(rèn)識。
說了這么多基礎(chǔ)的，就是要幫你對二叉樹建立正確的認(rèn)識，然后你會發(fā)現(xiàn)：
二叉樹的所有問題，就是讓你在前中后序位置注入巧妙的代碼logic，去達(dá)到自己的目的，你只需要單獨(dú)思考每一個節(jié)點(diǎn)應(yīng)該做什么，其他的不用你管，拋給二叉樹遍歷框架，遞歸會在所有節(jié)點(diǎn)上做相同的操作。
你也可以看到，固論牌法基礎(chǔ) 把二叉樹的追歷框架擴(kuò)展到了圈，并以追歷為基
---------
recursion 根據(jù)定義用語言表示出來：
---復(fù)習(xí)：
1、是否可以通過遍歷一遍二叉樹得到答案？如果可以，用一個?traverse?函數(shù)配合外部變量來實(shí)現(xiàn)。
2、是否可以定義一個遞歸函數(shù)，通過子問題（子樹）的答案推導(dǎo)出原問題的答案？如果可以，寫出這個遞歸函數(shù)的定義，并充分利用這個函數(shù)的返回值。
3、無論使用哪一種思維模式，你都要明白二叉樹的每一個節(jié)點(diǎn)需要做什么，需要在什么時候（前中后序）做。
這兩個問題的根本區(qū)別在于：一個節(jié)點(diǎn)在第幾層，你從根節(jié)點(diǎn)遍歷過來的過程就能順帶記錄，用遞歸函數(shù)的參數(shù)就能傳遞下去；而以一個節(jié)點(diǎn)為根的整棵子樹有多少個節(jié)點(diǎn)，你需要遍歷完子樹之后才能數(shù)清楚，然后通過遞歸函數(shù)的返回值拿到答案。
結(jié)合這兩個簡單的問題，你品味一下后序位置的特點(diǎn)，只有后序位置才能通過返回值獲取子樹的信息。
那么換句話說，一旦你發(fā)現(xiàn)題目和子樹有關(guān)，那大概率要給函數(shù)設(shè)置合理的定義和返回值，在后序位置寫代碼了。
---------搞懂了我之前覺得很餛飩的recursion
我求整棵樹中的最長「直徑」，那直截了當(dāng)?shù)乃悸肪褪潜闅v整棵樹中的每個節(jié)點(diǎn)，然后通過每個節(jié)點(diǎn)的左右子樹的最大深度算出每個節(jié)點(diǎn)的「直徑」，最后把所有「直徑」求個最大值即可。
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);
}
照應(yīng)一下前文：遇到子樹問題，首先想到的是給函數(shù)設(shè)置返回值，然后在后序位置做文章。
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;
}
}
