總結：二叉樹的屬性
theme: channing-cyan
持續創作，加速成長！這是我參與「掘金日新計劃 · 10 月更文挑戰」的第12天，點選檢視活動詳情
是否對稱
給定一個二叉樹，檢查它是否是映象對稱的。
上圖為對稱二叉樹
上圖的二叉樹則不是映象的
思路
判斷是否是映象，需要去判斷二叉樹的裡側和外側是否相同。
這就需要去判斷根節點下左子樹與右子樹裡側和外側是否相等。比較的方法是拿左子樹的 “左-右-中” 節點和右子樹的“右-左-中”為順序的節點做比較。
這題用遞迴的方式解比較方便，遞迴的思路如下： 1. 因為要比較倆個子樹是否是映象的，所以遞迴的引數為倆個，分別是左子樹節點和右子樹節點 2. 終止條件有三個：
- 左節點為空，右節點不為空，返回 false，左節點不為空，右節點為空，返回 false；
- 左右節點均不為空，但數值不同，返回 false；
-
如果左右節點均為空，則返回 true；
-
如果以上條件均不滿足，則再進入遞迴邏輯
程式碼實現
``` public boolean isSymmetric1(TreeNode root) { return compare(root.left, root.right); }
private boolean compare(TreeNode left, TreeNode right) {
if (left == null && right != null) {
return false;
}
if (left != null && right == null) {
return false;
}
if (left == null && right == null) {
return true;
}
if (left.val != right.val) {
return false;
}
// 比較外側
boolean compareOutside = compare(left.left, right.right);
// 比較內側
boolean compareInside = compare(left.right, right.left);
return compareOutside && compareInside;
}
```
時間複雜度：O(N)，其中 N 是樹的節點數。對每個節點訪問一次。
空間複雜度：O(H)，其中 H 是樹的高度
二叉樹的最大深度
給定一個二叉樹，找出其最大深度。
思路
二叉樹的深度是指根節點到最遠葉子節點的最長路徑上的節點數。
我們可以通過遞迴的方式求解此題：
- 遞迴函式的傳入的引數為二叉樹的根節點，返回值為二叉樹的高度；
- 遞迴的終止條件為當節點為空節點時，返回高度為 0；
- 先求出它左子樹的高度，然後再求出它右子樹的高度，倆高度的最大值+1為二叉樹的最大深度。
程式碼如下：
java
class solution {
public:
int getdepth(treenode node) {
if (node == null) return 0;
int leftdepth = getdepth(node.left); // 左
int rightdepth = getdepth(node.right); // 右
int depth = 1 + Math.max(leftdepth, rightdepth); // 中
return depth;
}
int maxdepth(treenode root) {
return getdepth(root);
}
};
時間複雜度：O(N)，其中 N 是樹的節點數。對每個節點訪問一次。
空間複雜度：O(H)，其中 H 是樹的高度
同理，該方法適用於求 N 叉樹的最大深度，程式碼如下：
```java
// Definition for a Node.
class Node {
public int val;
public List
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
class Solution {
public int maxDepth(Node root) {
if (root == null) {
return 0;
} else if (root.children.isEmpty()) {
return 1;
} else {
List
```
時間複雜度：O(N)，其中 N 是樹的節點數。對每個節點訪問一次。
空間複雜度：O(H)，其中 H 是樹的高度
二叉樹的最小深度
說明：最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
這裡有個誤區需要解釋一下，是從根節點到最近的葉子節點，如果根節點沒有左子樹或者右子樹，很多人就覺得最小深度為 1，這是不對的。是從根節點到最近葉子節點的最短路徑上的節點數量才是最小深度。
可以看出, 求二叉樹的最小深度和求二叉樹的最大深度的差別主要在於處理左右孩子不為空的邏輯。
程式碼如下：
java
class Solution {
/**
* 遞迴法，相比求MaxDepth要複雜點
* 因為最小深度是從根節點到最近**葉子節點**的最短路徑上的節點數量
*/
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null) {
return rightDepth + 1;
}
if (root.right == null) {
return leftDepth + 1;
}
// 左右結點都不為null
return Math.min(leftDepth, rightDepth) + 1;
}
}
時間複雜度：O(N)，其中 N 是樹的節點數。對每個節點訪問一次。
空間複雜度：O(H)，其中 H 是樹的高度。
求二叉樹有多少個節點
給出一個完全二叉樹，求出該樹的節點個數。
此題可用求二叉樹的最大深度的方式來求出，程式碼如下：
java
class solution {
public:
int getdepth(treenode node) {
if (node == null) return 0;
int leftdepth = getdepth(node.left); // 左
int rightdepth = getdepth(node.right); // 右
int depth = 1 + leftdepth, rightdepth; // 中
return depth;
}
int maxdepth(treenode root) {
return getdepth(root);
}
};
時間複雜度：O(n)，n 為二叉樹節點個數 空間複雜度：O(h)，h 為 樹的高度
平衡二叉樹
給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。
思路
既然是要求比較高度，則我們可以用到後序遍歷的方式。
- 明確遞迴函式的引數和返回值，引數為傳入的根節點，如果左右子樹的返回值 > 1,則我們返回 -1，表示已經不是平衡二叉樹了；
- 遞迴的終止條件為遇到了空節點，則 return 0, 表示當前節點為 根節點，高度為 0；
- 單層遞迴邏輯為，分別求出左右子樹的高度，如果差值小於等於 1，則返回當前二叉樹的高度，否則返回 -1，表示已經不是二叉樹了；
程式碼如下：
``` class Solution { /* * 遞迴法 / public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; }
private 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;
}
// 左右子樹高度差大於1，return -1表示已經不是平衡樹了
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
} ```
二叉樹的所有路勁
給定一個二叉樹，返回所有從根節點到葉子節點的路徑。
思路
根據題意要從根節點到葉子節點的路徑，所以需要前序遍歷。
- 確定遞迴的引數和返回值，引數為傳入的根節點，記錄每條路徑的節點值陣列path，以及路徑結果陣列res；
- 當遇到葉子節點的時候終止，並將路徑節點值數組裡的數值轉換成字串，然後加入到結果陣列；
- 遞迴的單層邏輯為，因為是前序遍歷：中-左-右，所以先處理中間節點，加入到 path 中，然後再遞迴處理左子樹和右子樹，並遞迴完後回溯；
程式碼如下：
```
//解法一
class Solution {
/*
* 遞迴法
/
public List
private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
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));
res.add(sb.toString());
return;
}
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);// 回溯
}
}
} ```
左葉子之和
計算給定二叉樹的所有左葉子之和。
思路
首先要判斷這棵二叉樹有沒有左葉子，就必須要通過節點的父節點來判斷其左孩子是不是左葉子，判斷程式碼如下：
if (root.left != null && root.left.left == null && root.left.right == null) { // 中
midValue = root.left.val;
}
用後序遍歷找出所有的左葉子節點數值之和，遞迴方式如下： 1. 遞迴函式的傳參為根節點，返回值為左葉子節點之和； 2. 遞迴終止條件為 root == null 返回 0； 3. 單層遞迴邏輯：當遇到左葉子節點的時候，記錄數值，然後通過遞迴求取左子樹左葉子之和，和 右子樹左葉子之和，相加便是整個樹的左葉子之和；
程式碼如下：
``` class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) return 0; int leftValue = sumOfLeftLeaves(root.left); // 左 int rightValue = sumOfLeftLeaves(root.right); // 右
int midValue = 0;
if (root.left != null && root.left.left == null && root.left.right == null) { // 中
midValue = root.left.val;
}
int sum = midValue + leftValue + rightValue;
return sum;
}
} ```
左下角的值
給定一個二叉樹，在樹的最後一行找到最左邊的值。
思路
本題比較容易下手的解題方式可以用層序遍歷的方法，找到最後一行的最左邊。
但是也可以用遞迴法來實現，首先可以明確深度最大的葉子節點一定是最後一行，那如何找最左邊的呢？我們可以使用前序遍歷，優先從左邊開始搜尋。
- 明確遞迴函式的引數和返回值：引數為傳入的根節點，以及一個int型變數用來記錄最長深度。返回值為 void；
- 當遇到葉子節點的時候，為終止條件，並開始統計最大深度；
- 確定單層遞迴邏輯，當不是葉子節點時，則繼續遍歷左子樹和右子樹，並記得要回溯；
程式碼如下：
```java // 遞迴法 class Solution { private int Deep = -1; private int value = 0; public int findBottomLeftValue(TreeNode root) { value = root.val; findLeftValue(root,0); return value; }
private void findLeftValue (TreeNode root,int deep) {
if (root == null) return;
if (root.left == null && root.right == null) {
if (deep > Deep) {
value = root.val;
Deep = deep;
}
}
if (root.left != null) findLeftValue(root.left,deep + 1);
if (root.right != null) findLeftValue(root.right,deep + 1);
}
} ```
路勁總和 1
給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等於目標和。
思路
利用遞迴來解答此題：
- 確定遞迴函式的傳參和返回值：引數為傳入的根節點和計數變數，該計數變數每次遞迴的時候需要減去當前節點的值，最後遇到葉子節點的時候判斷該葉子節點的值是否與它一致，如果一致，則表示找到了該路徑。返回值為bool型別；
- 遞迴函式的終止條件為：當遇到葉子節點的時候，並且計數變數等於葉子節點的值就返回 true;
- 單層遞迴邏輯為：遍歷左子樹和右子樹，並回溯
程式碼如下：
```java class solution { public boolean haspathsum(treenode root, int targetsum) { if (root == null) { return false; } targetsum -= root.val; // 葉子結點 if (root.left == null && root.right == null) { return targetsum == 0; } if (root.left != null) { boolean left = haspathsum(root.left, targetsum); if (left) {// 已經找到 return true; } } if (root.right != null) { boolean right = haspathsum(root.right, targetsum); if (right) {// 已經找到 return true; } } return false; } }
// 精簡後的程式碼
class solution { public boolean haspathsum(treenode root, int targetsum) {
if (root == null) return false; // 為空退出
// 葉子節點判斷是否符合
if (root.left == null && root.right == null) return root.val == targetsum;
// 求兩側分支的路徑和
return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
}
} ```
路徑總和2
給定一個二叉樹和一個目標和，找到所有從根節點到葉子節點路徑總和等於給定目標和的路徑。
思路
解題思路與上一題相似，只是需要記錄路徑。
程式碼如下：
```java
class solution {
public list
list<integer> path = new linkedlist<>();
preorderdfs(root, targetsum, res, path);
return res;
}
public void preorderdfs(treenode root, int targetsum, list<list<integer>> res, list<integer> path) {
path.add(root.val);
// 遇到了葉子節點
if (root.left == null && root.right == null) {
// 找到了和為 targetsum 的路徑
if (targetsum - root.val == 0) {
res.add(new arraylist<>(path));
}
return; // 如果和不為 targetsum，返回
}
if (root.left != null) {
preorderdfs(root.left, targetsum - root.val, res, path);
path.remove(path.size() - 1); // 回溯
}
if (root.right != null) {
preorderdfs(root.right, targetsum - root.val, res, path);
path.remove(path.size() - 1); // 回溯
}
}
} ```
我是傑少，如果您覺的我寫的不錯，那請給我 點贊+評論+收藏 後再走哦！
往期文章：
- 使用 Google Breakpad 來助力解決程式崩潰
- UE4 多人遊戲伺服器探索
- 使用虛幻引擎自動化工具實現自動化部署
- 如何在 UE4 中製作一扇自動開啟的大門
- 如何在 UE4 中用程式碼去控制角色移動
- 如何給 UE4 場景新增遊戲角色
- UE4：Android 平臺開發實踐指南
- UE4 開發避坑指南（持續更新）
- 新年開工啦，放個小煙花慶祝一下
- 聊聊與蘋果稽核員的愛恨情仇(下)
- 聊聊與蘋果稽核員的愛恨情仇(上)
- 一名普通工具人的 2021 | 2021年終總結
- 二叉樹刷題總結：二叉搜尋樹的屬性
- 二叉樹總結：二叉樹的屬性
- 二叉樹總結：二叉樹的修改與構造
- StoreKit2 有這麼香？嗯，我試過了，真香
- 看完這篇文章，再也不怕面試官問我如何構造二叉樹啦！
- 那幫做遊戲的又想讓大家氪金，太壞了！
- 手把手帶你擼一個網易雲音樂首頁 | 適配篇
- 手把手帶你擼一個網易雲音樂首頁（三）
- 手把手帶你擼一個網易雲音樂首頁（二）
- 手把手帶你擼一個網易雲音樂首頁（一）
- 程式碼要寫註釋嗎？寫你就輸了
- Codable釋出這麼久我就不學，摸魚爽歪歪，哎~就是玩兒
- iOS 優雅的處理網路資料，你真的會嗎？不如看看這篇
- UICollectionView 自定義佈局！看這篇就夠了
請你喝杯 ☕️ 點贊 + 關注哦～
- 閱讀完記得給我點個贊哦，有👍 有動力
- 關注公眾號--- HelloWorld傑少，第一時間推送新姿勢
最後，創作不易，如果對大家有所幫助，希望大家點贊支援，有什麼問題也可以在評論區裡討論😄～**
- 總結：二叉樹的屬性
- 雜湊表：數組合並總結
- 驗證與恢復二叉搜尋樹
- 二叉樹總結之最近公共祖先
- UE4 RPG 遊戲開發：簡單場景建立，角色資源匯入，移動參控繫結
- 使用虛幻引擎自動化工具實現自動化部署
- 你敢與人工智慧 Battle 一下五子棋嗎？反正我是沒贏過
- Codable釋出這麼久我就不學，摸魚爽歪歪，哎~就是玩兒
- 程式碼要寫註釋嗎？寫你就輸了
- iOS 優雅的處理網路資料，你真的會嗎？不如看看這篇.
- UE4：Android 平臺開發實踐指南
- 聊聊與蘋果稽核員的愛恨情仇(上)
- 一名普通工具人的 2021 | 2021年終總結
- 頭腦風暴之最近的請求次數
- 好看的圖表怎麼畫，看完這幾個 API 你就會了
- 動態規劃攻略之：下載外掛
- 動態規劃攻略之：傳遞資訊
- 動態規劃攻略之：獲取生成陣列中的最大值
- 動態規劃攻略之：用最小花費爬樓梯
- 動態規劃攻略之：楊輝三角