二叉樹的第三天彤守！
題目鏈接：110. 平衡二叉樹
狀態(tài)：不會毯侦，只知道平衡二叉樹的含義，不知道如何用代碼去判斷遗增，所以看解析叫惊。
但看了解析之后我又覺得，其實好像用已有知識是能做的做修，知識點就在昨天的筆記里了：既然要求高度霍狰，那就是用后序遍歷。接下來就是確認(rèn)遞歸三部曲了：1. 參數(shù)就是當(dāng)前節(jié)點饰及，返回值是當(dāng)前節(jié)點的樹高蔗坯。這里需要注意一個小細(xì)節(jié)，返回的樹高燎含，值有可能為-1宾濒，這一點在單層遞歸邏輯里會講述 2. 遞歸終止條件就是 遇到空節(jié)點時 就返回0，代表空節(jié)點的樹高為0屏箍。 3. 單層遞歸邏輯是判斷左子樹與右子樹的高度差绘梦，如果差值小于等于1，則返回該節(jié)點樹高赴魁；如果大于1卸奉，則返回-1表示此部分不為平衡二叉樹，因此隨著-1的層層返回颖御，最終整棵樹也不可能是平衡二叉樹榄棵。完整代碼如下：
class Solution { // Java
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
public int getHeight(TreeNode root){
if(root == null) return 0;
int leftHeight = getHeight(root.left);
if(leftHeight == -1) return -1;
int rightHeight = getHeight(root.right);
if(rightHeight == -1) return -1;
// If the height difference between the left and right subtrees is greater than 1,
// then we return -1, indicating that the tree is no longer balanced.
if(Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
}
復(fù)雜度分析：
時間復(fù)雜度：O(n). 因為每個節(jié)點會被訪問一次。
空間復(fù)雜度：O(h). 遞歸調(diào)用棧的深度取決于樹高h(yuǎn)，而空間復(fù)雜度取決于遞歸調(diào)用棧的深度疹鳄。
題目鏈接：257. 二叉樹的所有路徑
狀態(tài)：第一反應(yīng)是暴力法或者指針法拧略，第一反應(yīng)完全沒有二叉樹的方法，所以看解析瘪弓。
事實上這題是需要回溯操作的垫蛆，而遞歸和回溯本就是一家，所以本題很好腺怯。
- 遞歸函數(shù)參數(shù)以及返回值月褥。要傳入根節(jié)點，記錄每一條路徑的path和存放結(jié)果集的result瓢喉。所以不需要返回值
- 確定終止條件。與以往的if(cur == null){終止處理邏輯} 不同的是 我們遍歷到葉子節(jié)點即可舀透，而不用去遍歷到空節(jié)點栓票。因此正確寫法應(yīng)該是 if(cur.left == null && cur.right == null) {終止處理邏輯}
- 確定單層遞歸邏輯。遇到葉子節(jié)點愕够，我們就應(yīng)該記錄最后一個節(jié)點然后收集一個路徑走贪，接下來就是回溯了。具體代碼如下：注意遞歸和回溯是同時進(jìn)行的
class Solution { // Java
/**
* 遞歸法
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();// 存最終的結(jié)果
if (root == null) {
return res;
}
List<Integer> paths = new ArrayList<>();// 作為結(jié)果中的路徑
traversal(root, paths, res);
return res;
}
private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
paths.add(root.val);// 前序遍歷惑芭，中
// 遇到葉子結(jié)點
if (root.left == null && root.right == null) {
// 輸出
StringBuilder sb = new StringBuilder();// StringBuilder用來拼接字符串坠狡，速度更快
for (int i = 0; i < paths.size() - 1; i++) {
sb.append(paths.get(i)).append("->");
}
sb.append(paths.get(paths.size() - 1));// 記錄最后一個節(jié)點
res.add(sb.toString());// 收集一個路徑
return;
}
// 遞歸和回溯是同時進(jìn)行，所以要放在同一個花括號里
if (root.left != null) { // 左
traversal(root.left, paths, res);
paths.remove(paths.size() - 1);// 回溯
}
if (root.right != null) { // 右
traversal(root.right, paths, res);
paths.remove(paths.size() - 1);// 回溯
}
}
}
復(fù)雜度分析：
時間復(fù)雜度：O(n*h). 每個節(jié)點都要被訪問一次遂跟，同時每個葉子節(jié)點都要構(gòu)建一條從根節(jié)點到葉子節(jié)點的路徑逃沿，這個復(fù)雜度取決于樹高h(yuǎn)，所以最壞情況是這是一顆平衡樹即高度為O(n) 幻锁，在此情況下時間復(fù)雜度為O(n^2)
空間復(fù)雜度：O(n). 還是取決于遞歸深度凯亮，也就是取決于樹高。
