第六章?? 二叉樹part04

今日內容：?

1. ?110.平衡二叉樹?

1. ?257.?二叉樹的所有路徑?

1. ?404.左葉子之和?

?110.平衡二叉樹?（優先掌握遞歸）

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。

示例 1:

給定二叉樹 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

給定二叉樹 [1,2,2,3,3,null,null,4,4]

返回 false 。

遞歸法：

遞歸三步曲分析：

1. 明確遞歸函數的參數和返回值

參數：當前傳入節點。 返回值：以當前傳入節點為根節點的樹的高度。那么如何標記左右子樹是否差值大于1呢？

如果當前傳入節點為根節點的二叉樹已經不是二叉平衡樹了，還返回高度的話就沒有意義了。

所以如果已經不是二叉平衡樹了，可以返回-1 來標記已經不符合平衡樹的規則了。

1. 明確終止條件

遞歸的過程中依然是遇到空節點了為終止，返回0，表示當前節點為根節點的樹高度為0

1. 明確單層遞歸的邏輯

如何判斷以當前傳入節點為根節點的二叉樹是否是平衡二叉樹呢？當然是其左子樹高度和其右子樹高度的差值。

分別求出其左右子樹的高度，然后如果差值小于等于1，則返回當前二叉樹的高度，否則返回-1，表示已經不是二叉平衡樹了。

/**

?* 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.?二叉樹的所有路徑?

給定一個二叉樹，返回所有從根節點到葉子節點的路徑

這道題目要求從根節點到葉子的路徑，所以需要前序遍歷，這樣才方便讓父節點指向孩子節點，找到對應的路徑。

在這道題目中將第一次涉及到回溯，因為我們要把路徑記錄下來，需要回溯來回退一個路徑再進入另一個路徑。

遞歸

1. 遞歸函數參數以及返回值

要傳入根節點，記錄每一條路徑的path，和存放結果集的result，這里遞歸不需要返回值。

1. 確定遞歸終止條件

本題要找到葉子節點，就開始結束的處理邏輯了（把路徑放進result里）。

那么什么時候算是找到了葉子節點？?是當 cur不為空，其左右孩子都為空的時候，就找到葉子節點。

1. 確定單層遞歸邏輯

因為是前序遍歷，需要先處理中間節點，中間節點就是我們要記錄路徑上的節點，先放進path中。

然后是遞歸和回溯的過程，上面說過沒有判斷cur是否為空，那么在這里遞歸的時候，如果為空就不進行下一層遞歸了。

回溯和遞歸是一一對應的，有一個遞歸，就要有一個回溯。

/**

?* 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.左葉子之和?（優先掌握遞歸）

計算給定二叉樹的所有左葉子之和。

首先要注意是判斷左葉子，不是二叉樹左側節點，所以不要上來想著層序遍歷。

節點A的左孩子不為空，且左孩子的左右孩子都為空（說明是葉子節點），那么A節點的左孩子為左葉子節點

判斷當前節點是不是左葉子是無法判斷的，必須要通過節點的父節點來判斷其左孩子是不是左葉子。

遞歸法

遞歸的遍歷順序為后序遍歷（左右中），是因為要通過遞歸函數的返回值來累加求取左葉子數值之和。

遞歸三部曲：

1. 確定遞歸函數的參數和返回值

判斷一個樹的左葉子節點之和，那么一定要傳入樹的根節點，遞歸函數的返回值為數值之和，所以為int使用題目中給出的函數就可以了。

1. 確定終止條件

如果遍歷到空節點，那么左葉子值一定是0

只有當前遍歷的節點是父節點，才能判斷其子節點是不是左葉子。 所以如果當前遍歷的節點是葉子節點，那其左葉子也必定是0。

1. 確定單層遞歸的邏輯

當遇到左葉子節點的時候，記錄數值，然后通過遞歸求取左子樹左葉子之和，和 右子樹左葉子之和，相加便是整個樹的左葉子之和。

/**

?* 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;

? ? }

}