做供應(yīng)鏈的網(wǎng)站創(chuàng)建網(wǎng)站教程
第六章?? 二叉樹part04
今日內(nèi)容：?
- ?110.平衡二叉樹?
- ?257.?二叉樹的所有路徑?
- ?404.左葉子之和?
?110.平衡二叉樹?（優(yōu)先掌握遞歸）
給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過1。
示例 1:
給定二叉樹 [3,9,20,null,null,15,7]
返回 true 。
示例 2:
給定二叉樹 [1,2,2,3,3,null,null,4,4]
返回 false 。
遞歸法：
遞歸三步曲分析：
- 明確遞歸函數(shù)的參數(shù)和返回值
參數(shù)：當(dāng)前傳入節(jié)點。 返回值：以當(dāng)前傳入節(jié)點為根節(jié)點的樹的高度。那么如何標(biāo)記左右子樹是否差值大于1呢？
如果當(dāng)前傳入節(jié)點為根節(jié)點的二叉樹已經(jīng)不是二叉平衡樹了，還返回高度的話就沒有意義了。
所以如果已經(jīng)不是二叉平衡樹了，可以返回-1 來標(biāo)記已經(jīng)不符合平衡樹的規(guī)則了。
- 明確終止條件
遞歸的過程中依然是遇到空節(jié)點了為終止，返回0，表示當(dāng)前節(jié)點為根節(jié)點的樹高度為0
- 明確單層遞歸的邏輯
如何判斷以當(dāng)前傳入節(jié)點為根節(jié)點的二叉樹是否是平衡二叉樹呢？當(dāng)然是其左子樹高度和其右子樹高度的差值。
分別求出其左右子樹的高度，然后如果差值小于等于1，則返回當(dāng)前二叉樹的高度，否則返回-1，表示已經(jīng)不是二叉平衡樹了。
/**
?* Definition for a binary tree node.
?* public class TreeNode {
?* ? ? int val;
?* ? ? TreeNode left;
?* ? ? TreeNode right;
?* ? ? TreeNode() {}
?* ? ? TreeNode(int val) { this.val = val; }
?* ? ? TreeNode(int val, TreeNode left, TreeNode right) {
?* ? ? ? ? this.val = val;
?* ? ? ? ? this.left = left;
?* ? ? ? ? this.right = right;
?* ? ? }
?* }
?*/
class Solution {
? ? 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(Math.abs(leftHeight-rightHeight)>1) return -1;
? ? ? ? else return Math.max(leftHeight,rightHeight)+1;
? ? }
}
257.?二叉樹的所有路徑?
給定一個二叉樹，返回所有從根節(jié)點到葉子節(jié)點的路徑
思路
這道題目要求從根節(jié)點到葉子的路徑，所以需要前序遍歷，這樣才方便讓父節(jié)點指向孩子節(jié)點，找到對應(yīng)的路徑。
在這道題目中將第一次涉及到回溯，因為我們要把路徑記錄下來，需要回溯來回退一個路徑再進(jìn)入另一個路徑。
遞歸
- 遞歸函數(shù)參數(shù)以及返回值
要傳入根節(jié)點，記錄每一條路徑的path，和存放結(jié)果集的result，這里遞歸不需要返回值。
- 確定遞歸終止條件
本題要找到葉子節(jié)點，就開始結(jié)束的處理邏輯了（把路徑放進(jìn)result里）。
那么什么時候算是找到了葉子節(jié)點？?是當(dāng) cur不為空，其左右孩子都為空的時候，就找到葉子節(jié)點。
- 確定單層遞歸邏輯
因為是前序遍歷，需要先處理中間節(jié)點，中間節(jié)點就是我們要記錄路徑上的節(jié)點，先放進(jìn)path中。
然后是遞歸和回溯的過程，上面說過沒有判斷cur是否為空，那么在這里遞歸的時候，如果為空就不進(jìn)行下一層遞歸了。
回溯和遞歸是一一對應(yīng)的，有一個遞歸，就要有一個回溯。
/**
?* Definition for a binary tree node.
?* public class TreeNode {
?* ? ? int val;
?* ? ? TreeNode left;
?* ? ? TreeNode right;
?* ? ? TreeNode() {}
?* ? ? TreeNode(int val) { this.val = val; }
?* ? ? TreeNode(int val, TreeNode left, TreeNode right) {
?* ? ? ? ? this.val = val;
?* ? ? ? ? this.left = left;
?* ? ? ? ? this.right = right;
?* ? ? }
?* }
?*/
class Solution {
? ? public List<String> binaryTreePaths(TreeNode root) {
? ? ? ? List<String> result = new ArrayList<>();
? ? ? ? List<Integer> paths = new ArrayList<>();
? ? ? ? if(root==null) return result;
? ? ? ? travesal(root,result,paths);
? ? ? ? return result;
? ? }
? ? public void travesal(TreeNode root,List<String> result,List<Integer> paths)
? ? {
? ? ? ? paths.add(root.val);
? ? ? ? if(root.left==null&&root.right==null)
? ? ? ? {
? ? ? ? ? ? StringBuilder sb = new StringBuilder();
? ? ? ? ? ? for(int i=0;i<paths.size()-1;i++) ?sb.append(paths.get(i)).append("->");
? ? ? ? ? ? sb.append(paths.get(paths.size()-1));
? ? ? ? ? ? String path = sb.toString();
? ? ? ? ? ? result.add(path);
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? if(root.left!=null)
? ? ? ? {
? ? ? ? ? ? travesal(root.left,result,paths);
? ? ? ? ? ? paths.remove(paths.size()-1);
? ? ? ? }
? ? ? ? if(root.right!=null)
? ? ? ? {
? ? ? ? ? ? travesal(root.right,result,paths);
? ? ? ? ? ? paths.remove(paths.size()-1);
? ? ? ? }
? ? }
}
404.左葉子之和?（優(yōu)先掌握遞歸）
計算給定二叉樹的所有左葉子之和。
首先要注意是判斷左葉子，不是二叉樹左側(cè)節(jié)點，所以不要上來想著層序遍歷。
節(jié)點A的左孩子不為空，且左孩子的左右孩子都為空（說明是葉子節(jié)點），那么A節(jié)點的左孩子為左葉子節(jié)點
判斷當(dāng)前節(jié)點是不是左葉子是無法判斷的，必須要通過節(jié)點的父節(jié)點來判斷其左孩子是不是左葉子。
遞歸法
遞歸的遍歷順序為后序遍歷（左右中），是因為要通過遞歸函數(shù)的返回值來累加求取左葉子數(shù)值之和。
遞歸三部曲：
- 確定遞歸函數(shù)的參數(shù)和返回值
判斷一個樹的左葉子節(jié)點之和，那么一定要傳入樹的根節(jié)點，遞歸函數(shù)的返回值為數(shù)值之和，所以為int使用題目中給出的函數(shù)就可以了。
- 確定終止條件
如果遍歷到空節(jié)點，那么左葉子值一定是0
只有當(dāng)前遍歷的節(jié)點是父節(jié)點，才能判斷其子節(jié)點是不是左葉子。 所以如果當(dāng)前遍歷的節(jié)點是葉子節(jié)點，那其左葉子也必定是0。
- 確定單層遞歸的邏輯
當(dāng)遇到左葉子節(jié)點的時候，記錄數(shù)值，然后通過遞歸求取左子樹左葉子之和，和 右子樹左葉子之和，相加便是整個樹的左葉子之和。
/**
?* Definition for a binary tree node.
?* public class TreeNode {
?* ? ? int val;
?* ? ? TreeNode left;
?* ? ? TreeNode right;
?* ? ? TreeNode() {}
?* ? ? TreeNode(int val) { this.val = val; }
?* ? ? TreeNode(int val, TreeNode left, TreeNode right) {
?* ? ? ? ? this.val = val;
?* ? ? ? ? this.left = left;
?* ? ? ? ? this.right = right;
?* ? ? }
?* }
?*/
class Solution {
? ? public int sumOfLeftLeaves(TreeNode root) {
? ? ? ? if(root==null) return 0;
? ? ? ? if(root.left==null&&root.right==null) return 0;
? ? ? ? int leftSum = sumOfLeftLeaves(root.left);
? ? ? ? if(root.left!=null&&root.left.left==null&&root.left.right==null)
? ? ? ? leftSum = root.left.val;
? ? ? ? int rightSum = sumOfLeftLeaves(root.right);
? ? ? ? int sum = leftSum+rightSum;
? ? ? ? return sum;
? ? }
}