分門別類刷演算法，堅持，進步！
刷題路線參考：https://github.com/youngyangyang04/leetcode-master
大家好，我是拿輸出博客來督促自己刷題的老三，這一節我們來刷二叉樹，二叉樹相關題目在面試里非常高頻，而且在力扣里數量很多，足足有幾百道，不要慌，我們一步步來，我的文章很長，你們 收藏一下，
二叉樹基礎
二叉樹是一種比較常見的資料結構，在開始刷二叉樹之前，先簡單了解一下一些二叉樹的基礎知識，更詳細的資料結構知識建議學習《資料結構與演算法》，
什么是二叉樹
二叉樹是每個節點至多有兩棵子樹的樹，
二叉樹主要的兩種形式：滿二叉樹和完全二叉樹，
-
滿?叉樹：如果?棵?叉樹只有度為0的結點和度為2的結點，并且度為0的結點在同?層上，則這棵?
叉樹為滿?叉樹，一棵深度為k的滿二叉樹節點個數為2k -1，
-
完全?叉樹：至多只有最下面的兩層結點的度數可以小于 2, 并且最下一層上的結點都集中在該層最左邊的若干位置上， 則此二叉樹稱為完全二叉樹，
我們可以看出滿二叉樹是完全二叉樹， 但完全二叉樹不一定是滿二叉樹，
?叉搜索樹
?叉搜索樹，也可以叫二叉查找樹、二叉排序樹，是一種有序的二叉樹，它遵循著左小右大的規則：
- 若它的左?樹不空，則左?樹上所有結點的值均?于它的根結點的值；
- 若它的右?樹不空，則右?樹上所有結點的值均?于它的根結點的值；
- 它的左、右?樹也分別為?叉搜索樹
二叉樹存盤結構
和線性表類似，二叉樹的存盤結構也可采用順序存盤和鏈式存盤兩種方式，
順序存盤是將二叉樹所有元素編號，存入到一維陣列的對應位置，比較適合存盤滿二叉樹，
由于采用順序存盤結構存盤一般二叉樹造成大量存盤空間的浪費， 因此， 一般二叉樹的存盤結構更多地采用鏈式的方式，
二叉樹節點
我們在上面已經看了二叉樹的鏈式存盤，注意看，一個個節點是由三部分組成的，左孩子、資料、右孩子，
我們來定義一下二叉樹的節點節點：
/**
* @Author: 三分惡
* @Date: 2021/6/8
* @Description:
**/
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;
}
}
二叉樹遍歷方式
?叉樹主要有兩種遍歷?式：
-
深度優先遍歷：先往深?，遇到葉?節點再往回?，
-
?度優先遍歷：?層?層的去遍歷，
那么從深度優先遍歷和?度優先遍歷進?步拓展，才有如下遍歷?式：
-
深度優先遍歷
- 前序遍歷（遞回法，迭代法）
- 中序遍歷（遞回法，迭代法）
- 后序遍歷（遞回法，迭代法）
-
?度優先遍歷
- 層次遍歷（迭代法）
我們耳熟能詳的就是根、左、右三種遍歷，所謂根、左、右指的就是根節點的次序：
- 前序遍歷：根左右
- 中序遍歷：左根右
- 后序遍歷：左右根
還有一種更利于記憶的叫法：先根遍歷、中根遍歷、后根遍歷，這種說法就更一目了然了，
我們來看一個圖例：
具體的演算法實作主要有兩種方式：
- 遞回：樹本身就是一種帶著遞回性質的資料結構，使用遞回來實作深度優先遍歷還是非常方便的，
- 迭代：迭代需要借助其它的資料結構，例如堆疊來實作，
好了，我們已經了解了二叉樹的一些基礎知識，接下來，面對LeetCode的瘋狂打擊吧！
深度優先遍歷基礎
遞回基礎
二叉樹是一種天然遞回的資料結構，我們先簡單碰一碰遞回，
遞回有三大要素：
-
遞回函式的引數和回傳值
確定哪些引數是遞回的程序中需要處理的，那么就在遞回函式?加上這個引數， 并且還要明確每次遞回的回傳值是什么進?確定遞回函式的回傳型別，
-
終?條件：
遞回需要注意終止條件，終?條件或者終?條件寫的不對，作業系統的記憶體堆疊就會溢位，
-
單層遞回的邏輯
確定單層遞回的邏輯，在單層里會重復呼叫自己來實作遞回的程序，
好了，那么我們開始吧！
LeetCode144. 二叉樹的前序遍歷
那么先從二叉樹的前序遍歷開始吧，
? 題目：LeetCode144. 二叉樹的前序遍歷 (https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
? 難度：簡單
📕 描述：給你二叉樹的根節點 root ，回傳它節點值的 前序 遍歷，
💡 思路：
遞回法前序遍歷
我們前面看了遞回三要素，接下來我們開始用遞回法來進行二叉樹的前序遍歷：
- 確定遞回函式的引數和回傳值：因為要列印出前序遍歷節點的數值，所以引數?需要傳?List用來存放節點的數值；要傳入節點的值，自然也需要節點，那么遞回函式的引數就確定了；因為節點數值已經存在List里了，所以遞回函式回傳型別是void，代碼如下：
void preOrderRecu(TreeNode root, List<Integer> nodes)
- 確定終?條件：遞回結束也很簡單，如果當前遍歷的這個節點是空，就直接return，代碼如下：
//遞回結束條件
if (root == null) {
return;
}
- 確定單層遞回的邏輯：前序遍歷是根左右的順序，所以在單層遞回的邏輯里，先取根節點的值，再遞回左子樹和右子樹，代碼如下：
//添加根節點
nodes.add(root.val);
//遞回左子樹
preOrderRecu(root.left, nodes);
//遞回右子樹
preOrderRecu(root.right, nodes);
我們看一下二叉樹前序遍歷的完整代碼：
/**
* 二叉樹前序遍歷
*
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>(16);
preOrderRecu(root, nodes);
return nodes;
}
/**
* 二叉樹遞回前序遍歷
*
* @param root
* @param nodes
*/
void preOrderRecu(TreeNode root, List<Integer> nodes) {
//遞回結束條件
if (root == null) {
return;
}
//添加根節點
nodes.add(root.val);
//遞回左子樹
preOrderRecu(root.left, nodes);
//遞回右子樹
preOrderRecu(root.right, nodes);
}
單元測驗：
@Test
public void preorderTraversal() {
LeetCode144 l = new LeetCode144();
//構造二叉樹
TreeNode root = new TreeNode(1);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(3);
root.left = node1;
node1.right = node2;
//二叉樹先序遍歷
List<Integer> nodes = l.preorderTraversal(root);
nodes.stream().forEach(n -> {
System.out.print(n);
});
}
復雜度：
- 🚗 時間復雜度：O(n)，其中 n 是二叉樹的節點數，
遞回法會者不難，難者不會，只要能理解，這個是不是很輕松？😂
我們接下來，搞一下稍微麻煩一點的迭代法，
迭代法前序遍歷
迭代法的原理是引入新的資料結構，用來存盤遍歷的節點，
遞回的程序是不斷往左邊走，當遞回終止的時候，就添加節點，現在使用迭代，我們需要自己來用一個資料結構存盤節點，
那么用什么資料結構比較合適呢？我們自然而然地想到——堆疊，
迭代法的核心是： 借助堆疊結構，模擬遞回的程序，需要注意何時出堆疊入堆疊，何時訪問結點，
前序遍歷地順序是根左右，先把根和左子樹入堆疊，再將堆疊中的元素慢慢出堆疊，如果右子樹不為空，就把右子樹入堆疊，
ps：注意啊，我們的寫法將存盤元素進串列放在了堆疊操作前面，堆疊的作用主要用來找右子樹，
迭代和遞回究其本質是一樣的東西，不過遞回里這個堆疊由虛擬機幫我們隱式地管理了，
/**
* 二叉樹前序遍歷-迭代法
*
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>(16);
if (root == null) {
return nodes;
}
//使用鏈表作為堆疊
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while(root!=null || !stack.isEmpty()){
while(root!=null){
//根
nodes.add(root.val);
stack.push(root);
//左
root=root.left;
}
//出堆疊
root=stack.pop();
//右
root=root.right;
}
return nodes;
}
- 🚗時間復雜度：O(n)，其中 n 是二叉樹的節點數，每一個節點恰好被遍歷一次，
LeetCode94. 二叉樹的中序遍歷
? 題目：LeetCode94. 二叉樹的中序遍歷 (https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
? 難度：簡單
📕 描述：給你二叉樹的根節點 root ，回傳它節點值的 前序 遍歷，
- 遞回法中序遍歷
我們在前面已經用遞回法進行了二叉樹大的前序遍歷，中序遍歷類似，只是把根節點的次序放到中間而已，
/**
* 中序遍歷-遞回
*
* @param root
* @param nodes
*/
void inOrderRecu(TreeNode root, List<Integer> nodes) {
if (root == null) {
return;
}
//遞回左子樹
inOrderRecu(root.left, nodes);
//根節點
nodes.add(root.val);
//遞回右子樹
inOrderRecu(root.right, nodes);
}
-
迭代法中序遍歷
迭代法中序，也是使用堆疊來保存節點，
迭代法中序遍歷和前序遍歷類似，只是我們訪問節點的時機不同而已：
- 前序遍歷需要每次向左走之前就訪問根結點
- 而中序遍歷先壓堆疊，在出堆疊的時候才訪問
將節點的所有左孩子壓入堆疊中，然后出堆疊，出堆疊的時候將節點的值放入List，如果節點右孩子不為空，就處理右孩子，
/**
* 中序遍歷-迭代
*
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>(16);
if (root == null) {
return nodes;
}
//使用鏈表作為堆疊
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while (root != null || !stack.isEmpty()) {
//遍歷左子樹
while (root != null) {
stack.push(root);
root = root.left;
}
//取出堆疊中的節點
root = stack.pop();
//添加取出的節點
nodes.add(root.val);
//右子樹
root = root.right;
}
return nodes;
}
LeetCode145. 二叉樹的后序遍歷
? 題目：145. 二叉樹的后序遍歷 (https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
? 難度：簡單
📕 描述：給定一個二叉樹，回傳它的 后序 遍歷，
- 遞回法后序遍歷
遞回法，只要理解了可以說so easy了！
/**
* 二叉樹后序遍歷-遞回
*
* @param nodes
* @param root
*/
void postorderRecu(List<Integer> nodes, TreeNode root) {
if (root == null) {
return;
}
//遞回左子樹
postorderRecu(nodes, root.left);
//遞回右子樹
postorderRecu(nodes, root.right);
//根子樹
nodes.add(root.val);
}
- 迭代法后序遍歷
遞回法后序遍歷，可以用一個取巧的辦法，套用一下前序遍歷，前序遍歷是根左右，后序遍歷是左右根，我們只需要將前序遍歷的結果反轉一下，就是根左右，
如果使用Java實作，可以在鏈表上做文章，將尾插改成頭插也是一樣的效果，
/**
* 二叉樹后序遍歷-迭代
*
* @param root
* @return
*/
public List<Integer> postorderTraversal(TreeNode root) {
//使用鏈表作為堆疊
Deque<TreeNode> stack = new LinkedList<TreeNode>();
//節點
LinkedList<Integer> nodes = new LinkedList<Integer>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
//頭插法插入節點
nodes.addFirst(root.val);
//根節點入堆疊
stack.push(root);
//左子樹
root = root.left;
}
//節點出堆疊
root = stack.pop();
//右子樹
root = root.right;
}
return nodes;
}
當然，這是一種取巧的做法，你說這不是真正的迭代法后序遍歷，要真正的后序迭代二叉樹，也不復雜，
重點在于：
- 如果右子樹為慷訓者已經訪問過了才訪問根結點
- 否則，需要將該結點再次壓回堆疊中，去訪問其右子樹
/**
* 二叉樹后序遍歷-迭代-常規
*
* @param root
* @return
*/
public List<Integer> postorderTraversal1(TreeNode root) {
//使用鏈表作為堆疊
Deque<TreeNode> stack = new LinkedList<TreeNode>();
//節點值存盤
List<Integer> nodes = new ArrayList<>(16);
//用于記錄前一個節點
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
//根節點入堆疊
stack.push(root);
//左子樹
root = root.left;
}
//節點出堆疊
root = stack.pop();
//判斷節點右子樹是否為慷訓已經訪問過
if (root.right == null || root.right == pre) {
//添加節點
nodes.add(root.val);
//更新訪問過的節點
pre = root;
//使得下一次回圈直接出堆疊下一個
root = null;
} else {
//再次入堆疊
stack.push(root);
//訪問右子樹
root = root.right;
}
}
return nodes;
}
廣度優先遍歷基礎
LeetCode102. 二叉樹的層序遍歷
? 題目：102. 二叉樹的層序遍歷(https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
? 難度：中等
📕 描述：給你一個二叉樹，請你回傳其按 層序遍歷 得到的節點值， （即逐層地，從左到右訪問所有節點），
我們在前面已經使用迭代法完成了二叉樹的深度優先遍歷，現在我們來磕一下廣度優先遍歷，
在迭代法深度優先遍歷里，我們用了堆疊這種資料結構來存盤節點，那么層序遍歷這種一層一層遍歷的邏輯，適合什么資料結構呢？
答案是佇列，
那么層序遍歷的思路是什么呢？
使用佇列，把每一層的節點存盤進去，一層存盤結束之后，我們把佇列中的節點再取出來，左右孩子節點不為空，我們就把左右孩子節點放進去，
/**
* 二叉樹層序遍歷
*
* @param root
* @return
*/
public List<List<Integer>> levelOrder(TreeNode root) {
//結果集合
List<List<Integer>> result = new ArrayList<>(16);
if (root == null) {
return result;
}
//保存節點的佇列
Queue<TreeNode> queue = new LinkedList<>();
//加入根節點
queue.offer(root);
while (!queue.isEmpty()) {
//存放每一層節點的集合
List<Integer> level = new ArrayList<>(8);
//這里每層佇列的size要先取好，因為佇列是不斷變化的
int queueSize = queue.size();
//遍歷佇列
for (int i = 1; i <= queueSize; i++) {
//取出佇列的節點
TreeNode node = queue.poll();
//每層集合中加入節點
level.add(node.val);
//如果當前節點左孩子不為空，左孩子入隊
if (node.left != null) {
queue.offer(node.left);
}
//如果右孩子不為空，右孩子入隊
if (node.right != null) {
queue.offer(node.right);
}
}
//結果結合加入每一層結果集合
result.add(level);
}
return result;
}
- 🚗時間復雜度：每個點進隊出隊各一次，故漸進時間復雜度為 O(n)，
好了，二叉樹的深度優先遍歷和廣度優先遍歷的基礎已經完成了，接下來，我們看一看，在這兩種遍歷的基礎上衍生出的各種變化吧！
廣度優先遍歷基礎-變式
我們首先來看一下在層序遍歷的基礎上，稍微有一些變化的題目，
劍指 Offer 32 - I. 從上到下列印二叉樹
? 題目：劍指 Offer 32 - I. 從上到下列印二叉樹 (https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/)
? 難度：中等
📕 描述：從上到下列印出二叉樹的每個節點，同一層的節點按照從左到右的順序列印，
💡思路：
這道題可以說變化非常小了，
該咋做？
就這么做！
/**
* 從上到下列印二叉樹
*
* @param root
* @return
*/
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
List<Integer> nodes=new ArrayList<>(64);
//佇列
Deque<TreeNode> queue = new LinkedList<>();
//根節點
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
nodes.add(node.val);
//左孩子入隊
if (node.left != null) {
queue.offer(node.left);
}
//右孩子入隊
if (node.right != null) {
queue.offer(node.right);
}
}
//結果陣列
int[] result = new int[nodes.size()];
for (int i = 0; i < nodes.size(); i++) {
result[i] = nodes.get(i);
}
return result;
}
代碼沒改幾行，往里面套就完了，
劍指 Offer 32 - III. 從上到下列印二叉樹 III
? 題目：劍指 Offer 32 - III. 從上到下列印二叉樹 III(https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/)
? 難度：中等
📕 描述：請實作一個函式按照之字形順序列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右到左的順序列印，第三行再按照從左到右的順序列印，其他行以此類推，
💡思路：
這個題目的變化是奇數層要從左往右列印，偶數層要從右往左列印，
所以我們需要一個變數來記錄層級，
那什么資料結構既能從左往右插資料，又能從右往左插資料呢？
我們想到了雙向鏈表，
/**
* 劍指 Offer 32 - III. 從上到下列印二叉樹 III
*
* @param root
* @return
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>(32);
if (root == null) {
return result;
}
//佇列
Deque<TreeNode> queue = new LinkedList<>();
//根節點
queue.offer(root);
//記錄層級
int levelCount = 1;
while (!queue.isEmpty()) {
//當前佇列size
int queueSize = queue.size();
//使用雙向鏈表存盤每層節點
LinkedList<Integer> level = new LinkedList<>();
for (int i = 1; i <= queueSize; i++) {
//取節點
TreeNode node = queue.poll();
//判斷層級
//奇數，尾插
if (levelCount % 2 == 1) {
level.addLast(node.val);
}
//偶數，頭插
if (levelCount % 2 == 0) {
level.addFirst(node.val);
}
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
//右孩子
if (node.right != null) {
queue.offer(node.right);
}
}
//添加每層節點
result.add(level);
//層級增加
levelCount++;
}
return result;
}
LeetCode107. 二叉樹的層序遍歷 II
? 題目：107. 二叉樹的層序遍歷 II (https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)
? 難度：中等
📕 描述：給定一個二叉樹，回傳其節點值自底向上的層序遍歷， （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）
💡思路：
還記得我們后序遍歷二叉樹的取巧做法嗎？這不就是一回事嗎，層序遍歷，反轉List，或者用鏈表頭插每一層的集合，
/**
* 二叉樹的層序遍歷 II
*
* @param root
* @return
*/
public List<List<Integer>> levelOrderBottom(TreeNode root) {
//使用鏈表存盤結果，使用頭插法添加元素
LinkedList<List<Integer>> result = new LinkedList<>();
if (root == null) {
return result;
}
//佇列
Deque<TreeNode> queue = new LinkedList<>();
//插入根節點
queue.offer(root);
while (!queue.isEmpty()) {
//存放每一層節點的集合
List<Integer> level = new ArrayList<>(8);
//當前佇列size，需要取好，因為佇列在不斷變化
int currentQueueSize = queue.size();
//遍歷佇列
for (int i = 1; i <= currentQueueSize; i++) {
TreeNode node = queue.poll();
//每一層集合添加值
level.add(node.val);
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
//右孩子
if (node.right != null) {
queue.offer(node.right);
}
}
//頭插法插入每一層節點集合
result.addFirst(level);
}
return result;
}
LeetCode199. 二叉樹的右視圖
? 題目：199. 二叉樹的右視圖 (https://leetcode-cn.com/problems/binary-tree-right-side-view/)
? 難度：中等
📕 描述：給定一棵二叉樹，想象自己站在它的右側，按照從頂部到底部的順序，回傳從右側所能看到的節點值，
💡思路：
這個也很簡單對不對？
我們只需要判斷一下，節點是不是每層最后一個元素，是就加入集合，
怎么判斷？記得我們維護的有一個每層的元素個數變數嗎？拿這個判斷，
/**
* 二叉樹的右視圖
*
* @param root
* @return
*/
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>(16);
if (root == null) {
return result;
}
//佇列
Deque<TreeNode> queue = new LinkedList<>();
//根節點入隊
queue.offer(root);
while (!queue.isEmpty()) {
//維護佇列當前size
int queueCurrentSize = queue.size();
for (int i = 1; i <= queueCurrentSize; i++) {
//取出當前遍歷的節點
TreeNode node = queue.poll();
//判斷是否最右一個
if (i == queueCurrentSize) {
//結果集合添加節點值
result.add(node.val);
}
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
//右孩子
if (node.right != null) {
queue.offer(node.right);
}
}
}
return result;
}
LeetCode637. 二叉樹的層平均值
? 題目：637. 二叉樹的層平均值(https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/)
? 難度：簡單
📕 描述：給定一個非空二叉樹, 回傳一個由每層節點平均值組成的陣列，
每層求和，再除個節點個數，取個均值，
/**
* 637. 二叉樹的層平均值
*
* @param root
* @return
*/
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
if (root == null) {
return result;
}
//佇列
Deque<TreeNode> queue = new LinkedList<>();
//根節點
queue.offer(root);
while (!queue.isEmpty()) {
int currentQueueSize = queue.size();
//每一層值的總和
double levelSum = 0;
for (int i = 1; i <= currentQueueSize; i++) {
TreeNode node = queue.poll();
//累加
levelSum += node.val;
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
//平均值
double avg = levelSum / currentQueueSize;
//結果集合添加每層平均值
result.add(avg);
}
return result;
}
LeetCode429. N 叉樹的層序遍歷
? 題目：429. N 叉樹的層序遍歷(https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/)
? 難度：中等
📕 描述：給定一個 N 叉樹，回傳其節點值的層序遍歷，（即從左到右，逐層遍歷），
樹的序列化輸入是用層序遍歷，每組子節點都由 null 值分隔（參見示例），
和二叉樹的層序遍歷類似，不多樹變成了N叉樹，思路差不多，只不過左右子節點的入隊，變成了子節點集合節點的入隊，
/**
* 429. N 叉樹的層序遍歷
*
* @param root
* @return
*/
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>(16);
if (root == null) {
return result;
}
//佇列
Deque<Node> queue = new LinkedList<>();
//根節點
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>(8);
int currentQueueSize = queue.size();
for (int i = 1; i <= currentQueueSize; i++) {
Node node = queue.poll();
level.add(node.val);
//判斷子節點是否為空，添加子節點
if (!node.children.isEmpty()) {
queue.addAll(node.children);
}
}
//添加每層節點
result.add(level);
}
return result;
}
LeetCode515. 在每個樹行中找最大值
? 題目：515. 在每個樹行中找最大值 (https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/)
? 難度：中等
📕 描述：您需要在二叉樹的每一行中找到最大的值，
💡思路：
定義一個變數，來表示每層最大數，
/**
* 515. 在每個樹行中找最大值
*
* @param root
* @return
*/
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>(16);
if (root == null) {
return result;
}
//佇列
Deque<TreeNode> queue = new LinkedList<>();
//根節點
queue.offer(root);
while (!queue.isEmpty()) {
int queueSize = queue.size();
//最大值
Integer max = Integer.MIN_VALUE;
//遍歷一層
for (int i = 1; i <= queueSize; i++) {
//取節點
TreeNode node = queue.poll();
if (node.val > max) {
max = node.val;
}
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(max);
}
return result;
}
LeetCode116. 填充每個節點的下一個右側節點指標
? 題目：116. 填充每個節點的下一個右側節點指標 (https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/)
? 難度：中等
📕 描述：給定一個 完美二叉樹 ，其所有葉子節點都在同一層，每個父節點都有兩個子節點，二叉樹定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指標，讓這個指標指向其下一個右側節點，如果找不到下一個右側節點，則將 next 指標設定為 NULL，
初始狀態下，所有 next 指標都被設定為 NULL，
進階：
- 你只能使用常量級額外空間，
- 使用遞回解題也符合要求，本題中遞回程式占用的堆疊空間不算欄位外的空間復雜度，
💡思路：
這個思路也不難，我們增加一個變數來表示前一個節點，讓前一個節點的next指向當前節點，
/**
* 116. 填充每個節點的下一個右側節點指標
*
* @param root
* @return
*/
public Node connect(Node root) {
if (root == null) {
return root;
}
//佇列
Deque<Node> queue = new LinkedList();
//根節點
queue.offer(root);
while (!queue.isEmpty()) {
int queueSize = queue.size();
//前一個節點
Node pre = null;
for (int i = 0; i < queueSize; i++) {
Node node = queue.poll();
//每一層的第一個節點
if (i == 0) {
pre = node;
}
//讓前點左邊節點的next指向當前節點
if (i > 0) {
pre.next = node;
pre = node;
}
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
//右孩子
if (node.right != null) {
queue.offer(node.right);
}
}
}
return root;
}
LeetCode117. 填充每個節點的下一個右側節點指標 II
? 題目：117. 填充每個節點的下一個右側節點指標 II (https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/)
? 難度：中等
📕 描述：給定一個二叉樹
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指標，讓這個指標指向其下一個右側節點，如果找不到下一個右側節點，則將 next 指標設定為 NULL，
初始狀態下，所有 next 指標都被設定為 NULL，
💡思路：
和上一道題不是基本一模一樣嘛？除了不是完美二叉樹，但是不影響，一樣的代碼，
連續做了十道能用一個套路解決的問題，是不是瞬間有種神清氣爽，自信澎湃的感覺，我們繼續！
由于老三時間和水平有限，所以接下來的題目以遞回法為主，
二叉樹屬性
LeetCode101. 對稱二叉樹
? 題目：101. 對稱二叉樹 (https://leetcode-cn.com/problems/symmetric-tree/)
? 難度：簡單
📕 描述：給定一個二叉樹，檢查它是否是鏡像對稱的，
💡思路：
這題首先是要弄懂，這個鏡像對稱是什么鏡像？
判斷二叉樹對稱，比較的是兩棵樹（也就是根節點的左右子樹），
注意看，比較看的是T1左側的元素和T2的右側的元素；
以及T2左側的元素和T1右側的元素，
好了，我們現在看看遞回應該怎么實作，
-
遞回方法引數和回傳值
- 回傳值是是否對稱，就是布爾型別
- 要比較兩個子樹，所以引數是左子樹節點和右子樹節點
-
終止條件
- 都為空指標則回傳
true - 有一個為空則回傳
false - 兩個節點值不相等則回傳
false
- 都為空指標則回傳
-
遞回邏輯
- 判斷 T1 的右子樹與 T2 的左子樹是否對稱
- 判斷 T1 的左子樹與 T2 的右子樹是否對稱
最后要短路與，只有二者都回傳
true最終才為true
來看代碼：
/**
* 101. 對稱二叉樹
*
* @param root
* @return
*/
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
//呼叫遞回函式，比較左孩子，右孩子
return isSymmetric(root.left, root.right);
}
boolean isSymmetric(TreeNode left, TreeNode right) {
//遞回終止條件
//1、左右兩個節點都為空
if (left == null && right == null) {
return true;
}
//2、兩個節點中有一個為空
if (left == null || right == null) {
return false;
}
//3、兩個節點的值不相等
if (left.val != right.val) {
return false;
}
//遞回左節點的左孩子和右節點的右孩子
boolean outSide = isSymmetric(left.left, right.right);
//遞回左節點的右孩子和右節點的左孩子
boolean inSide = isSymmetric(left.right, right.left);
//兩種都對稱，樹才對稱
return outSide && inSide;
}
- 🚗時間復雜度：O(n)
LeetCode104. 二叉樹的最大深度
? 題目：104. 二叉樹的最大深度 (https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
? 難度：簡單
📕 描述：
給定一個二叉樹，找出其最大深度，
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，
說明: 葉子節點是指沒有子節點的節點，
💡思路：
這道題其實和后序遍歷類似，遞回左右子樹，求出左右子樹的深度，其中的最大值再加根節點的深度，
來看看遞回怎么寫：
-
入參、返參
- 入參是樹的根節點，表示樹
- 返參是樹的深度
-
終止條件
- 根節點為空，表示樹空
-
單層邏輯
- 求左子樹根的深度l
- 求右子樹的深度r
- 兩棵子樹深度的最大值再加上根節點深度，max(l,r)+1
來看代碼：
/**
* 104. 二叉樹的最大深度
*
* @param root
* @return
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
int maxDepth = Math.max(leftDepth, rightDepth) + 1;
return maxDepth;
}
- 🚗時間復雜度：O(n)
LeetCode 559. N 叉樹的最大深度
? 題目：559. N 叉樹的最大深度 (https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/)
? 難度：簡單
📕 描述：
給定一個 N 叉樹，找到其最大深度，
最大深度是指從根節點到最遠葉子節點的最長路徑上的節點總數，
N 叉樹輸入按層序遍歷序列化表示，每組子節點由空值分隔（請參見示例），
💡思路：
和上一道思路一樣，代碼如下：
/**
* 559. N 叉樹的最大深度
*
* @param root
* @return
*/
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
int maxDepth = 0;
for (int i = 0; i < root.children.size(); i++) {
int childrenDepth = maxDepth(root.children.get(i));
if (childrenDepth > maxDepth) {
maxDepth = childrenDepth;
}
}
return maxDepth + 1;
}
- 🚗時間復雜度：每個節點遍歷一次，所以時間復雜度是 O(N)，其中 NN 為節點數，
LeetCode111. 二叉樹的最小深度
? 題目：111. 二叉樹的最小深度 (https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/)
? 難度：簡單
📕 描述：
給定一個二叉樹，找出其最小深度，
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量，
**說明：**葉子節點是指沒有子節點的節點，
💡思路：
乍一看，暗喜，這不和二叉樹最大深度一樣嗎？
仔細一看，不對勁，
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量，
是到最近的葉子節點，如果子樹為空，那就沒有葉子節點，
所以在我們的單層邏輯里要考慮這種情況，代碼如下：
/**
* 111. 二叉樹的最小深度
*
* @param root
* @return
*/
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
//左子樹
int leftDepth = minDepth(root.left);
//左子樹
int rightDepth = minDepth(root.right);
//左子樹為空的情況
if (root.left == null && root.right != null) {
return rightDepth + 1;
}
//右子樹為空的情況
if (root.right == null && root.left != null) {
return leftDepth + 1;
}
return Math.min(leftDepth, rightDepth) + 1;
}
- 🚗時間復雜度：O(n)
LeetCode222. 完全二叉樹的節點個數
? 題目：222. 完全二叉樹的節點個數 (https://leetcode-cn.com/problems/count-complete-tree-nodes/)
? 難度：簡單
📕 描述：
給你一棵 完全二叉樹 的根節點 root ，求出該樹的節點個數，
完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其余每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若干位置，若最底層為第 h 層，則該層包含 1~ 2h 個節點，
**進階：**遍歷樹來統計節點是一種時間復雜度為 O(n) 的簡單解決方案，你可以設計一個更快的演算法嗎？
💡思路：
遞回方法：
如果要用遞回是不是挺簡單，左右子樹遞回，加上根節點，
/**
* 222. 完全二叉樹的節點個數
*
* @param root
* @return
*/
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftCount = countNodes(root.left);
int rightCount = countNodes(root.right);
return leftCount + rightCount + 1;
}
- 🚗時間復雜度：O(n)，
利用完全二叉樹特性：
我們先來回憶一下什么是完全二叉樹：若一棵二叉樹至多只有最下面的兩層結點的度數可以小于 2, 并且最下一層上的結點都集中在該層最左邊的若干位置上， 則此二叉樹稱為完全二叉樹，
完全二叉樹有兩種情況：
-
滿二叉樹
-
最后一層節點沒滿
第1種情況，節點個數=2^k-1（k為樹的深度，根節點的深度為0），
第2種情況，分別遞回左孩?，和右孩?，遞回到某?深度?定會有左孩?或者右孩?為滿?叉樹，節點數就可以用2^k-1，
只要樹不是滿二叉樹，就遞回左右孩子，知道遇到滿二叉樹，用公式計算子樹的節點數量，
代碼如下：
/**
* 222. 完全二叉樹的節點個數-利用完全二叉樹特性
*
* @param root
* @return
*/
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
//左孩子
TreeNode left = root.left;
//右孩子
TreeNode right = root.right;
int leftHeight = 0, rightHeight = 0;
// 求左?樹深度
while (left != null) {
left = left.left;
leftHeight++;
}
// 求右?樹深度
while (right != null) {
right = right.right;
leftHeight++;
}
//滿二叉樹
if (leftHeight == rightHeight) {
return (2 << leftHeight) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
- 🚗時間復雜度：O(logn * logn)
- 🏠 空間復雜度：O(logn)
LeetCode110. 平衡二叉樹
? 題目：110. 平衡二叉樹 (https://leetcode-cn.com/problems/balanced-binary-tree/)
? 難度：簡單
📕 描述：
給定一個二叉樹，判斷它是否是高度平衡的二叉樹，
本題中，一棵高度平衡二叉樹定義為：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 ，
💡思路：
在前面，我們做了一道題：104.二叉樹的最大深度 ，
平衡二叉樹的定義是一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 ，
那么我們思路就有了，用前序遍歷的方式去判斷一個節點以及節點的左右子樹是否平衡，
代碼如下：
/**
* 110. 平衡二叉樹
*
* @param root
* @return
*/
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
//左子樹高度
int leftDepth = depth(root.left);
//右子樹高度
int rightDepth = depth(root.right);
//當前節點
boolean isRootBalanced = Math.abs(leftDepth - rightDepth) <= 1;
//遞回左子樹
boolean isLeftBalanced = isBalanced(root.left);
//遞回右子樹
boolean isRightBalaced = isBalanced(root.right);
//平衡
return isRootBalanced && isLeftBalanced && isRightBalaced;
}
/**
* 獲取子樹高度
*
* @param root
* @return
*/
public int depth(TreeNode root) {
if (root == null) {
return 0;
}
//左子樹高度
int leftDepth = depth(root.left);
//右子樹高度
int rightDepth = depth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
- 🚗 時間復雜度：獲取子樹高度時間復雜度O(n)，判斷平衡又要不斷遞回左右子樹，所以時間復雜度為O(n2)，
這種是一種時間復雜度略高的方式，是一種從上往下的判斷方式，
還有一種方式，從下往上，類似于二叉樹的后序遍歷，
/**
* 110. 平衡二叉樹-從下往上
*
* @param root
* @return
*/
public boolean isBalanced(TreeNode root) {
return helper(root) != -1;
}
public int helper(TreeNode root) {
if (root == null) {
return 0;
}
//不平衡直接回傳-1
//左子樹
int left = helper(root.left);
//左子樹不平衡
if (left == -1) {
return -1;
}
//右子樹
int right = helper(root.right);
//右子樹不平衡
if (right == -1) {
return -1;
}
//如果左右子樹都是平衡二叉樹
//判斷左右子樹高度差是否小于1
if (Math.abs(left - right) > 1) {
return -1;
}
//回傳二叉樹中節點的最大高度
return Math.max(left, right) + 1;
}
- 🚗時間復雜度：因為從下往上，每個節點只會遍歷到一次，所以時間復雜度為O(n)，
LeetCode404. 左葉子之和
? 題目：404. 左葉子之和(https://leetcode-cn.com/problems/sum-of-left-leaves/)
? 難度：簡單
📕 描述：
計算給定二叉樹的所有左葉子之和，
💡思路：
這道題題號很危險，但其實不難，重點在于搞清楚什么是左葉子節點？
-
首先，這個節點得是父節點的左孩子，
-
其次，這個節點得是葉子節點，
把這點搞清楚以后，就是一個前序遍歷，代碼如下：
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
//判斷根節點的左孩子是否為左葉子
if (root.left != null && root.left.left == null && root.left.right == null) {
sum = root.left.val;
}
//遞回左右子樹
return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
- 🚗 時間復雜度：O(n)，
LeetCode513. 找樹左下角的值
? 題目：513. 找樹左下角的值 (https://leetcode-cn.com/problems/find-bottom-left-tree-value/)
? 難度：簡單
📕 描述：
給定一個二叉樹，在樹的最后一行找到最左邊的值，
💡思路：
這道題用廣度優先遍歷比較簡單，前面我們已經做過十道廣度優先遍歷的題目，這里就不再贅言，上代碼：
public int findBottomLeftValue(TreeNode root) {
if (root == null) {
return 0;
}
int bottomLeftValue = 0;
//保存節點的佇列
Queue<TreeNode> queue = new LinkedList<>();
//加入根節點
queue.offer(root);
while (!queue.isEmpty()) {
int currentSize = queue.size();
//取出佇列中的節點
for (int i = 0; i < currentSize; i++) {
//取出隊中節點
TreeNode node = queue.poll();
//每層最左邊節點
if (i == 0) {
//賦值
bottomLeftValue = node.val;
}
//當前節點左孩子入隊
if (node.left != null) {
queue.offer(node.left);
}
//當前節點右孩子入隊
if (node.right != null) {
queue.offer(node.right);
}
}
}
return bottomLeftValue;
}
- 🚗時間復雜度：O(n)，
二叉樹路徑問題
LeetCode257. 二叉樹的所有路徑
? 題目：257. 二叉樹的所有路徑 (https://leetcode-cn.com/problems/binary-tree-paths/)
? 難度：簡單
📕 描述：
給定一個二叉樹，回傳所有從根節點到葉子節點的路徑，
說明: 葉子節點是指沒有子節點的節點，
💡思路：
可以使用深度優先遍歷的方式處理這道題——前序遍歷，遞回，我們都寫熟了的，
但是，這道題不僅僅是遞回，還隱藏了回溯，
類比一下我們平時走路，假如說從一個路口，我們想走完所有路口，那么我們該怎么走呢？
那就是我們先沿著一個路口走到頭，再回到上一個路口，走另外一個方向，
對于這道題目，回溯的示意圖如下：
看一下代碼：
/**
* @return java.util.List<java.lang.String>
* @Description: 二叉樹的所有路徑-回溯初版
* @author 三分惡
* @date 2021/7/14 8:28
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>(32);
if (root == null) {
return result;
}
LinkedList path = new LinkedList();
traversal(root, path, result);
return result;
}
/**
* @return void
* @Description: 遍歷
* @author 三分惡
* @date 2021/7/14 8:29
*/
void traversal(TreeNode current, LinkedList path, List<String> result) {
path.add(current.val);
//葉子節點
if (current.left == null && current.right == null) {
StringBuilder sPath = new StringBuilder();
for (int i = 0; i < path.size() - 1; i++) {
sPath.append(path.get(i));
//這個箭頭不能忘
sPath.append("->");
}
sPath.append(path.get(path.size() - 1));
result.add(sPath.toString());
return;
}
//遞回左子樹
if (current.left != null) {
traversal(current.left, path, result);
//回溯
path.removeLast();
}
//遞回右子樹
if (current.right != null) {
traversal(current.right, path, result);
//回溯
path.removeLast();
}
}
精簡一下也是可以的，不過回溯就隱藏了：
/**
* @return java.util.List<java.lang.String>
* @Description: 257. 二叉樹的所有路徑
* https://leetcode-cn.com/problems/binary-tree-paths/
* @author 三分惡
* @date 2021/7/11 10:11
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>(32);
if (root == null) {
return result;
}
traversal(root, "", result);
return result;
}
/**
* @return void
* @Description: 遍歷
* @author 三分惡
* @date 2021/7/11 10:10
*/
void traversal(TreeNode current, String path, List<String> result) {
path += current.val;
//葉子節點
if (current.left == null && current.right == null) {
//將路徑加入到結果中
result.add(path);
return;
}
//遞回左子樹
if (current.left != null) {
traversal(current.left, path + "->", result);
}
//遞回右子樹
if (current.right != null) {
traversal(current.right, path + "->", result);
}
}
- 🚗 時間復雜度：O(n2)，其中n表示節點數目，在深度優先搜索中每個節點會被訪問一次且只會被訪問一次，每一次會對 path 變數進行拷貝構造，時間代價為 O(n)，所以時間復雜度為O(n^2)，
LeetCode112. 路徑總和
? 題目：112. 路徑總和 (https://leetcode-cn.com/problems/path-sum/)
? 難度：簡單
📕 描述：
給你二叉樹的根節點 root 和一個表示目標和的整數 targetSum ，判斷該樹中是否存在 根節點到葉子節點 的路徑，這條路徑上所有節點值相加等于目標和 targetSum ，
葉子節點 是指沒有子節點的節點，
💡思路：
既然路徑問題已經開始，我們就連做幾道來鞏固一下，
一樣的思路：遞回遍歷+回溯
代碼如下：
/**
* @return boolean
* @Description:
* @author 三分惡
* @date 2021/7/13 8:34
*/
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return traversal(root, targetSum - root.val);
}
/**
* @return boolean
* @Description: 遍歷
* @author 三分惡
* @date 2021/7/14 21:22
*/
boolean traversal(TreeNode current, int count) {
//終止條件
if (current.left == null && current.right == null && count == 0) {
//葉子節點，且計數為0
return true;
}
if (current.left == null && current.right == null) {
//葉子節點
return false;
}
//左子樹
if (current.left != null) {
count -= current.left.val;
if (traversal(current.left, count)) {
return true;
}
//回溯，撤銷處理結果
count += current.left.val;
}
//右子樹
if (current.right != null) {
count -= current.right.val;
if (traversal(current.right, count)) {
return true;
}
count += current.right.val;
}
return false;
}
簡化一波，如下：
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return traversal(root, targetSum);
}
private boolean traversal(TreeNode root, int count) {
if (root == null) {
return false;
}
//找到滿足條件路徑
if (root.left == null && root.right == null && count == root.val) {
return true;
}
return traversal(root.left, count - root.val) || traversal(root.right, count - root.val);
}
- 🚗 時間復雜度：和上一道題一樣，O(n2)，
LeetCode113. 路徑總和 II
? 題目：113. 路徑總和 II (https://leetcode-cn.com/problems/path-sum-ii/)
? 難度：中等
📕 描述：
給你二叉樹的根節點 root 和一個整數目標和 targetSum ，找出所有 從根節點到葉子節點 路徑總和等于給定目標和的路徑，
葉子節點 是指沒有子節點的節點，
💡思路：
好家伙，這道題不是結合了257和112嘛！
直接先上遞回+回溯，
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
//結果
List<List<Integer>> result = new ArrayList<>(32);
if (root == null) {
return result;
}
//路徑
LinkedList<Integer> path = new LinkedList();
traversal(root, path, result, targetSum - root.val);
return result;
}
private void traversal(TreeNode root, LinkedList<Integer> path, List<List<Integer>> result, int count) {
//根節點放入路徑
path.add(root.val);
//葉子節點,且滿足節點總和要求
if (root.left == null && root.right == null && count == 0) {
//注意，這里需要新定義一個path集合,否則result里存盤的是path的參考
List<Integer> newPath = new LinkedList<>(path);
//添加路徑
result.add(newPath);
return;
}
//如果是葉子節點，直接回傳
if (root.left == null && root.right == null) {
return;
}
//遞回左子樹
if (root.left != null) {
count -= root.left.val;
traversal(root.left, path, result, count);
//回溯
path.removeLast();
count += root.left.val;
}
//遞回右子樹
if (root.right != null) {
count -= root.right.val;
traversal(root.right, path, result, count);
//回溯
path.removeLast();
count += root.right.val;
}
}
接下來簡化一下：
//結果
List<List<Integer>> result = new ArrayList<>(16);
//路徑
LinkedList<Integer> path = new LinkedList<>();
/**
* @return java.util.List<java.util.List < java.lang.Integer>>
* @Description: 113. 路徑總和 II
* @author 三分惡
* @date 2021/7/12 21:25
*/
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return result;
}
traversal(root, targetSum);
return result;
}
/**
* @return void
* @Description: 深度優先遍歷
* @author 三分惡
* @date 2021/7/12 22:03
*/
void traversal(TreeNode root, int sum) {
if (root == null) {
return;
}
//路徑和
sum -= root.val;
//添加節點
path.offerLast(root.val);
//到達葉子節點,且路徑和滿足要求
if (root.left == null && root.right == null && sum == 0) {
result.add(new LinkedList<>(path));
}
//遞回左子樹
traversal(root.left, sum);
//遞回右子樹
traversal(root.right, sum);
//回溯
path.pollLast();
}
- 🚗時間復雜度：一樣，O(n^2)，
LeetCode437. 路徑總和 III
? 題目：437. 路徑總和 III (https://leetcode-cn.com/problems/path-sum-iii/)
? 難度：中等
📕 描述：
給定一個二叉樹，它的每個結點都存放著一個整數值，
找出路徑和等于給定數值的路徑總數，
路徑不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（只能從父節點到子節點），
二叉樹不超過1000個節點，且節點數值范圍是 [-1000000,1000000] 的整數，
💡思路：
這道題不需要從根節點開始，也不需要在葉子節點結束，所以呢，
- 我們要遍歷每一個節點，要額外遞回一次
- 獲取到符合條件的path，也不要return
下面上代碼，直接上精簡版的，看了前面一道題，相信原始版遞回+回溯 也是小case，
//結果
int result = 0;
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
//根節點
traversal(root, targetSum);
//左子樹遞回
pathSum(root.left, targetSum);
//右子樹遞回
pathSum(root.right, targetSum);
return result;
}
/**
* @return void
* @Description: 深度優先遍歷
* @author 三分惡
* @date 2021/7/12 22:03
*/
void traversal(TreeNode root, int sum) {
if (root == null) {
return;
}
//路徑和
sum -= root.val;
//不需要到達葉子節點,路徑和滿足要求即可
if (sum == 0) {
//結果添加
result++;
}
//遞回左子樹
traversal(root.left, sum);
//遞回右子樹
traversal(root.right, sum);
}
- 🚗時間復雜度：pathSum會遍歷每一個節點，時間復雜度為O(n)，traversal 時間復雜度為O(n)，所以時間復雜度為O(n2)，
有一道題 ——面試題 04.12. 求和路徑 (https://leetcode-cn.com/problems/paths-with-sum-lcci/) 和這道題基本一模一樣，
?叉樹的修改與構造
LeetCode 106. 從中序與后序遍歷序列構造二叉樹
? 題目：106. 從中序與后序遍歷序列構造二叉樹 (https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
? 難度：中等
📕 描述：
根據一棵樹的中序遍歷與后序遍歷構造二叉樹，
注意:
你可以假設樹中沒有重復的元素，
💡思路：
我們首先來看一棵樹，中序遍歷和后序遍歷是什么樣
我們根據中序遍歷和后序遍歷的特性，可以得出：
- 在后序遍歷序列中，最后一個元素是樹的根節點
- 在中序遍歷序列中，根節點的左邊是左子樹，根節點的右邊是右子樹
那么我們怎么還原二叉樹呢？
可以拿后序序列的最后一個節點去切分中序序列，然后根據中序序列，再反過來切分后序序列，這樣一層一層地切下去，每次后序序列的最后一個元素就是節點的元素，
我們看一下這個程序：
那具體的步驟是什么樣呢？
- 如果陣列長度為0，說明是空節點，
- 如果不為空，那么取后序陣列最后一個元素作為節點元素
- 找到后序陣列最后一個元素在中序陣列的位置，作為切割點
- 切割中序陣列，切成中序左陣列（左子樹）和中序右陣列（右子樹）
- 切割后序陣列，切成后序左陣列和后序右陣列
- 遞回左、右區間
這里又存在一個問題，我們需要確定，下一輪的起點和終點，
我們拿[inStart，inEnd] 標記中序陣列起始和終止位置，拿[postStart，postEnd]標記后序陣列起止位置，rootIndex標記根節點位置，
- 左子樹-中序陣列
inStart = inStart,inEnd = rootIndex - 1 - 左子樹-后序陣列
postSrart = postStart,postEnd = postStart + ri - is - 1(pe計算程序解釋，后續陣列的起始位置加上左子樹長度-1 就是后后序陣列結束位置了，左子樹的長度 = 根節點索引-左子樹) - 右子樹-中序陣列
inStart = roootIndex + 1, inEnd = inEnd - 右子樹-后序陣列
postStart = postStart + rootIndex - inStart, postEnd - 1
![樹的計算程序-來源參考[7]](https://img.uj5u.com/2021/09/04/2615230407113354.png)
代碼如下：
/**
* 106. 從中序與后序遍歷序列構造二叉樹
* https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
* @param inorder
* @param postorder
* @return
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0 || postorder.length == 0) return null;
return buildTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
/**
* @param inorder 中序陣列
* @param inStart 中序陣列起點
* @param inEnd 中序陣列終點
* @param postorder 后序陣列
* @param postStart 后序陣列起點
* @param postEnd 后序陣列終點
* @return
*/
public TreeNode buildTree(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
//沒有元素
if (inEnd - inStart < 1) {
return null;
}
//只有一個元素
if (inEnd - inStart == 1) {
return new TreeNode(inorder[inStart]);
}
//后序陣列最后一個元素就是根節點
int rootVal = postorder[postEnd - 1];
TreeNode root = new TreeNode(rootVal);
int rootIndex = 0;
//根據根節點，找到該值在中序陣列inorder里的位置
for (int i = inStart; i < inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
}
}
//根據rootIndex切割左右子樹
root.left = buildTree(inorder, inStart, rootIndex,
postorder, postStart, postStart + (rootIndex - inStart));
root.right = buildTree(inorder, rootIndex + 1, inEnd,
postorder, postStart + (rootIndex - inStart), postEnd - 1);
return root;
}
- 🚗 時間復雜度O(n)，
LeetCode105. 從前序與中序遍歷序列構造二叉樹
? 題目：105. 從前序與中序遍歷序列構造二叉樹 (https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
? 難度：中等
📕 描述：
給定一棵樹的前序遍歷 preorder 與中序遍歷 inorder，請構造二叉樹并回傳其根節點，
💡思路：
和上一道題目類似，先序遍歷第一個節點是根節點，拿先序遍歷陣列第一個元素去切割中序陣列，再拿中序陣列切割先序陣列，
代碼如下：
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, 0, preorder.length-1,
inorder, 0, inorder.length-1);
}
public TreeNode buildTree(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
//遞回終止條件
if (inStart > inEnd || preStart > preEnd) return null;
//根節點值
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
//根節點下標
int rootIndex = inStart;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
//遞回，尋找左右子樹
root.left=buildTree(preorder, preStart + 1, preStart + (rootIndex - inStart),
inorder, inStart, rootIndex - 1);
root.right=buildTree(preorder, preStart + (rootIndex - inStart) + 1, preEnd,
inorder, rootIndex + 1, inEnd);
return root;
}
🚗 時間復雜度：O(n)
LeetCode654. 最大二叉樹
? 題目：654. 最大二叉樹 (https://leetcode-cn.com/problems/maximum-binary-tree/)
? 難度：中等
📕 描述：
給定一個不含重復元素的整數陣列 nums ，一個以此陣列直接遞回構建的 最大二叉樹 定義如下：
- 二叉樹的根是陣列 nums 中的最大元素，
- 左子樹是通過陣列中 最大值左邊部分 遞回構造出的最大二叉樹，
- 右子樹是通過陣列中 最大值右邊部分 遞回構造出的最大二叉樹，
回傳有給定陣列 nums 構建的 最大二叉樹 ，
示例 1：
輸入：nums = [3,2,1,6,0,5]
輸出：[6,3,5,null,2,0,null,null,1]
解釋：遞回呼叫如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左邊部分是 [3,2,1] ，右邊部分是 [0,5] ，
- [3,2,1] 中的最大值是 3 ，左邊部分是 [] ，右邊部分是 [2,1] ，
- 空陣列，無子節點，
- [2,1] 中的最大值是 2 ，左邊部分是 [] ，右邊部分是 [1] ，
- 空陣列，無子節點，
- 只有一個元素，所以子節點是一個值為 1 的節點，
- [0,5] 中的最大值是 5 ，左邊部分是 [0] ，右邊部分是 [] ，
- 只有一個元素，所以子節點是一個值為 0 的節點，
- 空陣列，無子節點，
示例 2：
輸入：nums = [3,2,1]
輸出：[3,null,2,null,1]
💡 思路：
這個就好說了，題目里面都給出了解法，nums最大元素是根節點，然后再遞回最大元素左右部分，
代碼如下：
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree(nums, 0, nums.length);
}
public TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {
//沒有元素
if (end - start < 1) {
return null;
}
//只剩一個元素
if (end - start == 1) {
return new TreeNode(nums[start]);
}
//最大值位置
int maxIndex = start;
//最大值
int maxVal = nums[start];
for (int i = start + 1; i < end; i++) {
if (nums[i] > maxVal) {
maxVal = nums[i];
maxIndex = i;
}
}
//根節點
TreeNode root = new TreeNode(maxVal);
//遞回左半部分
root.left = constructMaximumBinaryTree(nums, start, maxIndex);
//遞回右半部分
root.right = constructMaximumBinaryTree(nums, maxIndex + 1, end);
return root;
}
- 🚗 時間復雜度 ：找到陣列最大值時間復雜度O(n)，遞回時間復雜度O(n)，所以總的時間復雜度O(n2)，
LeetCode617. 合并二叉樹
? 題目：617. 合并二叉樹 (https://leetcode-cn.com/problems/merge-two-binary-trees/)
? 難度：簡單
📕 描述：
給定兩個二叉樹，想象當你將它們中的一個覆寫到另一個上時，兩個二叉樹的一些節點便會重疊，
你需要將他們合并為一個新的二叉樹，合并的規則是如果兩個節點重疊，那么將他們的值相加作為節點合并后的新值，否則不為 NULL 的節點將直接作為新二叉樹的節點，
示例 1:
輸入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
輸出:
合并后的樹:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必須從兩個樹的根節點開始，
💡思路：
做個簡單題找下信心，
這道題啥情況呢？
這不就前序遍歷根、左、右嘛，
雖然題目里沒要求不能改變原來的樹結構，但是，我們還是用一棵新樹來合并兩棵樹，
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//遞回結束條件，有一個節點為空
if (root1 == null || root2 == null) {
return root1 == null ? root2 : root1;
}
//新樹
TreeNode root = new TreeNode(0);
//合并
root.val = root1.val + root2.val;
//左子樹
root.left = mergeTrees(root1.left, root2.left);
//右子樹
root.right = mergeTrees(root1.right, root2.right);
return root;
}
- 🚗 時間復雜度：O(n)，
求?叉搜索樹的屬性
二叉搜索樹我們前面也了解了，左小右大，接下來我們開始看看二叉搜索樹相關題目，
LeetCode700. 二叉搜索樹中的搜索
? 題目：700. 二叉搜索樹中的搜索 (https://leetcode-cn.com/problems/search-in-a-binary-search-tree/)
? 難度：簡單
📕 描述：
給定二叉搜索樹（BST）的根節點和一個值， 你需要在BST中找到節點值等于給定值的節點， 回傳以該節點為根的子樹， 如果節點不存在，則回傳 NULL，
例如，
給定二叉搜索樹:
4
/ \
2 7
/ \
1 3
和值: 2
你應該回傳如下子樹:
2
/ \
1 3
在上述示例中，如果要找的值是 5，但因為沒有節點值為 5，我們應該回傳 NULL，
💡 思路：
這也沒啥好說的吧，前序遍歷就行了，
只不過遞回左右子樹的時候，我們可以利用左小右大的特性，
📜代碼如下：
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
//遞回左子樹
if (val < root.val) {
return searchBST(root.left, val);
}
//遞回右子樹
if (val > root.val) {
return searchBST(root.right, val);
}
return null;
}
- 🚗 時間復雜度：O(logn)，
LeetCode98. 驗證二叉搜索樹
? 題目：98. 驗證二叉搜索樹(https://leetcode-cn.com/problems/validate-binary-search-tree/)
? 難度：簡單
📕 描述：
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹，
假設一個二叉搜索樹具有如下特征：
- 節點的左子樹只包含小于當前節點的數，
- 節點的右子樹只包含大于當前節點的數，
- 所有左子樹和右子樹自身必須也是二叉搜索樹，
示例 1:
輸入:
2
/ \
1 3
輸出: true
示例 2:
輸入:
5
/ \
1 4
/ \
3 6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]，
根節點的值為 5 ，但是其右子節點值為 4 ，
💡 思路：
我們知道，中序遍歷二叉搜索樹，輸出的是有序序列，所以上中序遍歷，
在root比較的時候呢，我們可以把root和上一個root比較，
📜代碼如下：
class Solution {
private TreeNode pre;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
//左子樹
boolean isValidLeft = isValidBST(root.left);
if (!isValidLeft){
return false;
}
//根
if (pre!=null&&pre.val>=root.val){
return false;
}
pre=root;
//右子樹
boolean isValidRight = isValidBST(root.right);
return isValidRight;
}
}
- 🚗 時間復雜度O(n)
LeetCode530. 二叉搜索樹的最小絕對差
? 題目：98. 驗證二叉搜索樹(https://leetcode-cn.com/problems/validate-binary-search-tree/)
? 難度：簡單
📕 描述：
給你一棵所有節點為非負值的二叉搜索樹，請你計算樹中任意兩節點的差的絕對值的最小值，
示例：
輸入：
1
\
3
/
2
輸出：
1
解釋：
最小絕對差為 1，其中 2 和 1 的差的絕對值為 1（或者 2 和 3），
💡 思路：
二叉搜索樹的中序遍歷是有序的，
那和上一道題一樣，中序遍歷，我們同樣記錄上一個遍歷的節點，然后取和當前節點差值的最大值，
📜代碼如下：
class Solution {
TreeNode pre;
Integer res = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
dfs(root);
return res;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
//左
getMinimumDifference(root.left);
//中
if (pre != null) {
res = Math.min(res, root.val-pre.val);
}
pre=root;
//右
getMinimumDifference(root.right);
}
}
- 🚗 時間復雜度O(n)
LeetCode501. 二叉搜索樹中的眾數
? 題目：501. 二叉搜索樹中的眾數 (https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/)
? 難度：簡單
📕 描述：
給定一個有相同值的二叉搜索樹（BST），找出 BST 中的所有眾數（出現頻率最高的元素），
假定 BST 有如下定義：
- 結點左子樹中所含結點的值小于等于當前結點的值
- 結點右子樹中所含結點的值大于等于當前結點的值
- 左子樹和右子樹都是二叉搜索樹
例如：
給定 BST [1,null,2,2],
1
\
2
/
2
回傳[2].
提示：如果眾數超過1個，不需考慮輸出順序
**進階：**你可以不使用額外的空間嗎？（假設由遞回產生的隱式呼叫堆疊的開銷不被計算在內
💡 思路：
如果是二叉樹求眾數，我們能想到的辦法就是引入map來統計高頻元素集合，
但是二叉搜索樹，我們接著用它的中序遍歷有序這個特性，
用prev表示前一個節點，用count表示當前值的數量，用maxCount表示重復數字的最大數量，使用串列存盤結果，
-
如果節點值等于prev，count就加1，
-
如果節點不等于prev，說明遇到了下一個新的值，更新prev為新的值，然后讓count=1；
- 如果count==maxCount，就把當前節點的值加入到集合list中，
- 如果count>maxCount，先把list集合清空，然后再把當前節點的值加入到集合list中，最后在更新maxCount的值，
📜代碼如下：
class Solution {
//記錄當前個數
int count = 0;
//最大個數
int maxCount = 1;
//前驅
TreeNode pre=new TreeNode(0);
//存盤眾數串列
List<Integer> res = new ArrayList<>();
public int[] findMode(TreeNode root) {
dfs(root);
int[] ans = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
ans[i] = res.get(i);
}
return ans;
}
public void dfs(TreeNode root) {
if (root == null) return;
//左
dfs(root.left);
//中
if (root.val == pre.val) {
//如果和前一個相同，count++
count++;
} else {
//否則
//pre往后
pre = root;
//count重繪為1
count = 1;
}
//如果是出現次數最多的值
if (count == maxCount) {
res.add(root.val);
} else if (count > maxCount) {
//如果超過最多出現次數
//清空結果結合
res.clear();
//加入新的max元素
res.add(root.val);
//重繪max計數
maxCount = count;
}
//右
dfs(root.right);
}
}
- 🚗 時間復雜度：O(n)
- 🏠 空間復雜度：O(n)
?叉樹公共祖先問題
LeetCode236. 二叉樹的最近公共祖先
? 題目：501. 二叉搜索樹中的眾數 (https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/)
? 難度：簡單
📕 描述：
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先，
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”
示例 1：
輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出：3
解釋：節點 5 和節點 1 的最近公共祖先是節點 3 ，
示例 2：
輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出：5
解釋：節點 5 和節點 4 的最近公共祖先是節點 5 ，因為根據定義最近公共祖先節點可以為節點本身，
💡 思路：
我們想啊，查找公共祖先，要是我們能從兩個節點往回走就好了，
那有什么辦法呢？
還記得我們前面做路徑問題的時候嗎？我們用到了一個方法——回溯，
大家看一下這個順序是什么？左、右、根,這不是后序遍歷嘛！
那怎么判斷一個節點是節點q和節點p的公共祖先呢？有哪幾種情況呢？
- q和q都是該節點的子樹，而且異側（p左q右或者p右q左）
- q在p的子樹中
- q在p的子樹中
那這個后序的遞回，又該怎么寫呢？
我們看看遞回三要素[8]：
- 入參和回傳值
需要遞回函式回傳節點值，來告訴我們是否找到節點q或者p，
- 終止條件
如果找到了 節點p或者q，或者遇到空節點，就回傳，
- 單層遞回邏輯
我們需要判斷是否找到了p和q.
-
當 leftleftleft 和 rightrightright 同時為空 ：說明 root的左 / 右子樹中都不包含 p,q，回傳 null；
-
當 left 和 right 同時不為空 ：說明 p,q 分列在 root 的 異側 （分別在 左 / 右子樹），因此 root為最近公共祖先，回傳 root
-
當 leftleftleft 為空 ，right不為空 ：p,q 都不在 root的左子樹中，直接回傳 right，具體可分為兩種情況：
- p,q 其中一個在 root 的 右子樹 中，此時 right指向 p（假設為 p ）
- p,q 兩節點都在 root的 右子樹 中，此時的 right 指向 最近公共祖先節點
-
當 left不為空 ， right為空 ：與情況
3.同理；
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遞回結束條件
if (root == null || root == p || root == q) return root;
//左
TreeNode left = lowestCommonAncestor(root.left, p, q);
//右
TreeNode right = lowestCommonAncestor(root.right, p, q);
//四種情況判斷
//left和right同時為空
if (left == null && right == null) {
return null;
}
//left和right同時不為空
if (left != null && right != null) {
return root;
}
//left為空，right不為空
if (left == null && right != null) {
return right;
}
//left不為空，right為空
if (left != null && right == null) {
return left;
}
return null;
}
精簡一下代碼：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遞回結束條件
if (root == null || root == p || root == q) return root;
//左
TreeNode left = lowestCommonAncestor(root.left, p, q);
//右
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
if (left == null) return right;
return left;
}
- 🚗 時間復雜度：O(n)，
LeetCode235. 二叉搜索樹的最近公共祖先
? 題目：501. 二叉搜索樹中的眾數 (https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/)
? 難度：簡單
📕 描述：
給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先，
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”
例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節點 2 和節點 8 的最近公共祖先是 6，
示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節點 2 和節點 4 的最近公共祖先是 2, 因為根據定義最近公共祖先節點可以為節點本身，
說明:
- 所有節點的值都是唯一的，
- p、q 為不同節點且均存在于給定的二叉搜索樹中，
💡 思路：
接著我們來看二叉搜索樹的最近公共祖先，我們可以直接用二叉樹的最近公共祖先的方法給它來一遍，
但是有沒有可能能利用到我們二叉搜索樹的特性呢？
當然可以，
我們的二叉樹的節點是左小右大的特性，只要當前節點在[p,q]之間，就可以確定當前節點是最近公共祖先，
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
//左
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
//右
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
- 🚗 時間復雜度：O(n)
?叉搜索樹的修改與構造
LeetCode701. 二叉搜索樹中的插入操作
? 題目：701. 二叉搜索樹中的插入操作 (https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
? 難度：中等
📕 描述：
給定二叉搜索樹（BST）的根節點和要插入樹中的值，將值插入二叉搜索樹， 回傳插入后二叉搜索樹的根節點， 輸入資料 保證 ，新值和原始二叉搜索樹中的任意節點值都不同，
注意，可能存在多種有效的插入方式，只要樹在插入后仍保持為二叉搜索樹即可， 你可以回傳 任意有效的結果 ，
示例 1：
輸入：root = [4,2,7,1,3], val = 5
輸出：[4,2,7,1,3,5]
解釋：另一個滿足題目要求可以通過的樹是：
💡 思路：
注意：這道題是沒有限制插入的方式的，
像題目示例中，給出了兩種情況：
- 第一種：占別人的位置，可以看到5和4的位置做了調整，讓樹滿足平衡二叉樹的要求，但是這種實作起來肯定麻煩
- 第二種：我們其實可以偷個懶，找個空位唄，我們通過搜索，找到一個符合大小關系的葉子節點，把它插入到葉子節點的子樹，
代碼如下：
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
//左
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
}
//右
if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}
return root;
}
- 🚗 時間復雜度：O(n)，
LeetCode450. 洗掉二叉搜索樹中的節點
? 題目：701. 二叉搜索樹中的插入操作 (https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
? 難度：中等
📕 描述：
給定一個二叉搜索樹的根節點 root 和一個值 key，洗掉二叉搜索樹中的 key 對應的節點，并保證二叉搜索樹的性質不變，回傳二叉搜索樹（有可能被更新）的根節點的參考，
一般來說，洗掉節點可分為兩個步驟：
- 首先找到需要洗掉的節點；
- 如果找到了，洗掉它，
說明： 要求演算法時間復雜度為 O(h)，h 為樹的高度，
示例:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
給定需要洗掉的節點值是 3，所以我們首先找到 3 這個節點，然后洗掉它，
一個正確的答案是 [5,4,6,2,null,null,7], 如下圖所示，
5
/ \
4 6
/ \
2 7
另一個正確答案是 [5,2,6,null,4,null,7]，
5
/ \
2 6
\ \
4 7
💡 思路：
哦吼，上道題我們偷了懶，但是這道題沒法偷懶了，
洗掉一個節點，就相當于挖了個坑，我們就得想辦法把它填上，而且還得讓二叉樹符合平衡二叉樹的定義，
找到洗掉節點，我們把所有的情況列出來：
- 左右孩子都為空（葉子節點），直接洗掉節點
- 洗掉節點的左孩子為空，右孩子不為空，洗掉節點，右孩子補位
- 洗掉節點的右孩子為空，左孩子不為空，洗掉節點，左孩子補位
被洗掉節點左右孩子節點都不為空，則將洗掉節點的左子樹頭結點（左孩子），放到洗掉節點的右子樹的最左節點的左孩子上，這句話很繞對不對，我們拿圖說話，
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
//找到被洗掉節點
if (root.val == key) {
//1. 左右孩子都為空（葉子節點）
if (root.left == null && root.right == null) return null;
//2. 左孩子為空，右孩子不為空
if (root.left == null) return root.right;
//3. 右孩子為空，左孩子不空
if (root.right == null) return root.left;
//4.左右孩子都不為空
if (root.left != null && root.right != null) {
//尋找右子樹最左節點
TreeNode node = root.right;
while (node.left != null) {
node = node.left;
}
//把要洗掉節點的左子樹放在node左子樹位置
node.left = root.left;
//把root節點保存一下，準備洗掉
TreeNode temp = root;
//root右孩子作為新的根節點
root = root.right;
return root;
}
}
//左孩子
if (key < root.val) root.left = deleteNode(root.left, key);
//右孩子
if (key > root.val) root.right = deleteNode(root.right, key);
return root;
}
代碼點臃腫，但是每種情況都很清晰，懶得再精簡了，
- 🚗 時間復雜度：O(n)，
LeetCode669. 修剪二叉搜索樹
? 題目：701. 二叉搜索樹中的插入操作 (https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
? 難度：中等
📕 描述：
給你二叉搜索樹的根節點 root ，同時給定最小邊界low 和最大邊界 high，通過修剪二叉搜索樹，使得所有節點的值在[low, high]中，修剪樹不應該改變保留在樹中的元素的相對結構（即，如果沒有被移除，原有的父代子代關系都應當保留）， 可以證明，存在唯一的答案，
所以結果應當回傳修剪好的二叉搜索樹的新的根節點，注意，根節點可能會根據給定的邊界發生改變，
示例 1：
輸入：root = [1,0,2], low = 1, high = 2
輸出：[1,null,2]
示例 2：
輸入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
輸出：[3,2,null,1]
💡 思路：
修剪的示意圖：
大概的程序是什么樣呢？
遍歷二叉樹：
- 當前節點如果是在[low，high]內，繼續向下遍歷
- 當前節點小于low時候，是需要剪枝的節點，查找它的右子樹，找到在[low，high]區間的節點
- 如果當前節點大于high的時候，是需要剪枝的節點，查找它的左子樹，找到在[low，high]區間的節點
代碼如下：
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
if (root.val < low) {
return trimBST(root.right, low, high);
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
- 🚗 時間復雜度：O(n)，
LeetCode538. 把二叉搜索樹轉換為累加樹
? 題目：701. 二叉搜索樹中的插入操作 (https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
? 難度：中等
📕 描述：
給出二叉 搜索 樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（Greater Sum Tree），使每個節點 node 的新值等于原樹中大于或等于 node.val 的值之和，
提醒一下，二叉搜索樹滿足下列約束條件：
- 節點的左子樹僅包含鍵 小于 節點鍵的節點，
- 節點的右子樹僅包含鍵 大于 節點鍵的節點，
- 左右子樹也必須是二叉搜索樹，
💡思路：
這個題怎么辦呢？
如果是陣列[3,5,6] 我們馬上就能想到，從后往前累加唄，
但是這是個二叉搜索樹，我們知道二叉搜索樹的中序序列是一個有序序列，那我們把中序倒過來不就行了，
中序是左、右、中,我們改成右、中、左，
class Solution {
int preVal = 0;
public TreeNode convertBST(TreeNode root) {
dfs(root);
return root;
}
public void dfs(TreeNode root) {
if (root == null) return;
//倒中序，右左中
dfs(root.right);
root.val += preVal;
preVal = root.val;
dfs(root.left);
}
}
- 🚗 時間復雜度：O(n)，
總結
順口溜總結來了：
簡單的事情重復做，重復的事情認真做，認真的事情有創造性地做！
我是
三分惡，一個能文能武的全堆疊開發，
點贊、關注不迷路，大家下期見！
博主是個演算法萌新，刷題思路和路線主要參考了以下大佬！建議關注！
參考：
[1]. https://github.com/youngyangyang04/leetcode-master
[2]. https://labuladong.gitbook.io/algo/
[3]. https://leetcode-cn.com/u/sdwwld/
[4]. https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/qing-song-ji-yi-er-cha-shu-de-qian-zhong-6vu5/
[5]. https://leetcode-cn.com/problems/binary-tree-paths/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-5f58/
[6]. https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/
[7].https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/tu-jie-gou-zao-er-cha-shu-wei-wan-dai-xu-by-user72/
[8].https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/
[9]. https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/javachao-jian-dan-de-er-fen-sou-suo-di-g-z83v/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297291.html
標籤：其他
上一篇：資料結構之堆以及topk問題