目录
讀題
104.二叉树的最大深度
自己看到题目的第一想法
這道題目昨天用層序遍歷的時候有做過,在想法上就是迭代到最後一層的時候返回的不是數組,而是當下的深度,深度則可以在每一次遞迴的時候depth + 1 ,就可以求到了。
111.二叉树的最小深度
自己看到题目的第一想法
這道題目昨天用層序遍歷的時候有做過,在想法上就是只要遇到一個節點的左右子樹都為空時,直接回傳當下的深度,因為這時就在這棵樹的最小深度了。
看完代码随想录之后的想法
在實作遞迴的時候反而卡住了,看完之後才知道我應該要對左右子樹其中一個為空的狀況進行判斷,不能直接使用min,看完之後對於題目的定義比較清晰
222.完全二叉树的节点个数
自己看到题目的第一想法
看到題目,想到之前有講到的完全二叉樹與滿二叉樹的差別,完全二叉樹是只要非葉子節點,那數量一定是滿的,如果是葉子節點的話就要由左到右,中間不能為空,
其實整體跟深度很像,只是深度是在第一個回圈++,個數則是在第二個回圈就要++
迭代跟遞迴的作法基本上跟最大深度的做法沒有差太多
104.二叉树的最大深度 - 實作
遞迴思路
錯誤思路
- 傳入的參數值
- root → 從根結點開始遞迴,之後到每個節點
- depth 深度值
- 終止條件
- if (root == null)
- 單遞迴條件
- if(root→right) treveral(root→right, depth+1);
- if(root→left)treveral(root→left, depth+1
錯誤點: 這不是迭代,並且左右子樹的深度有可能不一樣,所以應該是要分為左右子樹分別去底下找最後比較大小,另外傳入值只需要cur,因為return 就是depth值
正確思路
- 傳入的參數值
- root → 從根結點開始遞迴,之後到每個節點
- 終止條件
- if (root == null) return 0 —> 因為是int,須返回整數值
- 單遞迴條件
- int leftdepth = findMaxDepth(cur→left);
- int rightdepth = findMaxDepth(cur→right);
- int depth = 1 + max(leftdepth, rightdepth);
- return depth
錯誤點: 這不是迭代,並且左右子樹的深度有可能不一樣,所以應該是要分為左右子樹分別去底下找最後比較大小,另外傳入值只需要cur,因為return 就是depth值
迭代思路
- 設置一個queue來暫存每一層的元素
- 設定depth = 0; → 紀錄深度
- 進入回圈
假設queue不為空 → 代表目前仍有節點
設置size = que.size() -> 代表每層的個數
設立一個回圈size--
- 使用建立一個節點暫存node
- 將queue的元素pop出來
- 將暫存的左右子樹假設不為空則加入到queue當中
<aside> 💡 為甚麼不是直接que.size()-- 是因為que.size會一直變動,而size其實所存的只有每一層的個數,所以每次回圈的size都會是該層的元素個數
</aside>
遞迴代碼
錯誤代碼
class Solution {
public:
int findMaxDepth(TreeNode* cur, int depth) {
if(cur == NULL) return depth;
if(cur->left) findMaxDepth(cur->right, depth+1);
if(cur->right) findMaxDepth(cur->left, depth+1);
return depth;
}
int maxDepth(TreeNode* root) {
int depth = 0;
findMaxDepth(root, depth);
return depth;
}
};
正確代碼
class Solution {
public:
int findMaxDepth(TreeNode* cur) {
if(cur == NULL) return 0 ;
int leftdepth = findMaxDepth(cur->left);
int rightdepth = findMaxDepth(cur->right);
int depth = 1 + max(leftdepth, rightdepth);
return depth;
}
int maxDepth(TreeNode* root) {
int depth = findMaxDepth(root);;
return depth;
}
};
迭代代碼
class Solution {
public:
int maxDepth(TreeNode* root) {
queue<TreeNode*> que;
if(root != NULL) que.push(root);
int depth = 0;
while(!que.empty()) {
int size = que.size();
while(size--) {
TreeNode* node = que.front();
que.pop();
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
depth++;
}
return depth;
}
};
111.二叉树的最小深度 - 實作
遞迴思路
錯誤思路
- 傳入的參數值
- root → 從根結點開始遞迴,之後到每個節點
- depth → 因為要記錄目前走到哪一層
- 終止條件
- if (root == null) return 0 —> 因為是int,須返回整數值
- if(!node→right && !node→left) return depth;
- 單遞迴條件
- leftdepth = findMinDepth(cur->left, depth + 1);
- rightdepth = findMinDepth(cur->right, depth + 1);
- return 1 + min(leftdepth, rightdepth); → 1 代表第一層
錯誤點: 這是要求根結點到葉節點的最小距離,所以需要去判斷左右子樹是否為空,如果都不為空我才去抓左右子樹的最小節點。
正確思路
- 傳入的參數值
- root → 從根結點開始遞迴,之後到每個節點
- 終止條件
- if (root == null) return 0 —> 因為是int,須返回整數值
- 單遞迴條件
- leftdepth = findMinDepth(cur->left);
- rightdepth = findMinDepth(cur->right);
- if(cur→left && !cur→right) return 1 + rightdepth;
- if(!cur→left && cur→right) return 1 + leftdepth;
- return 1 + min(leftdepth, rightdepth); → 1 代表第一層
- return depth
錯誤點: 這是要求根結點到葉節點的最小距離,所以需要去判斷左右子樹是否為空,如果都不為空我才去抓左右子樹的最小節點。
迭代思路
錯誤思路
- 設置一個queue來暫存每一層的元素
- 設定depth = 0; → 紀錄深度
- 進入回圈
假設queue不為空 → 代表目前仍有節點
設置size = que.size() -> 代表每層的個數
設立一個回圈size--
- 使用建立一個節點暫存node
- 將queue的元素pop出來
- 假設某一個節點左右子樹都為空,則直接return 該層深度
- 將暫存的左右子樹假設不為空則加入到queue當中
跳出後depth++
<aside> 💡 為甚麼不是直接que.size()-- 是因為que.size會一直變動,而size其實所存的只有每一層的個數,所以每次回圈的size都會是該層的元素個數
</aside>
錯誤點: 應該在假設不為空的時候就直接depth++,因為在最大深度這樣做沒有關係,但是假設在最小深度,要馬return 時要加一,要馬調換順序
正確思路
- 設置一個queue來暫存每一層的元素
- 設定depth = 0; → 紀錄深度
- 進入回圈
- 假設queue不為空 → 代表目前仍有節點
- Depth++
- 設置size = que.size() -> 代表每層的個數
- 設立一個回圈size--
- 使用建立一個節點暫存node
- 將queue的元素pop出來
- 假設某一個節點左右子樹都為空,則直接return 該層深度
- 將暫存的左右子樹假設不為空則加入到queue當中
遞迴代碼
錯誤代碼
class Solution {
public:
int findMinDepth(TreeNode* cur, int depth) {
if(cur == NULL) return 0 ;
if(!cur->left && !cur->right) return depth;
int leftdepth = findMinDepth(cur->left, depth + 1);
int rightdepth = findMinDepth(cur->right, depth + 1);
return 1 + min(leftdepth, rightdepth);
}
int minDepth(TreeNode* root) {
int depth = findMinDepth(root, 0);
return depth;
}
};
正確代碼
class Solution {
public:
int findMinDepth(TreeNode* cur) {
if(cur == NULL) return 0 ;
int leftdepth = findMinDepth(cur->left);
int rightdepth = findMinDepth(cur->right);
if(!cur->left && cur->right)return 1 + rightdepth;
if(cur->left && !cur->right)return 1 + leftdepth;
return 1 + min(leftdepth, rightdepth);
}
int minDepth(TreeNode* root) {
return findMinDepth(root);
}
};
迭代代碼
class Solution {
public:
int maxDepth(TreeNode* root) {
queue<TreeNode*> que;
if(root != NULL) que.push(root);
int depth = 0;
while(!que.empty()) {
int size = que.size();
while(size--) {
TreeNode* node = que.front();
que.pop();
if(!node->left && !node->right) return depth;
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
depth++;
}
return depth;
}
};
222.完全二叉树的节点个数 - 實作
思路
遞迴思路
- 傳入值 root ,回傳int
- 終止條件: root == NULL , return 0 ;
- 遞迴
- 記錄左子樹的count
- 紀錄右子樹的count
- 最後return 1 + 左count + 右 count
迭代思路
- 建立一個queue來儲存暫時元素
- 建立一個count紀錄目前元素數量
- while回圈條件當!que.empty()
- 建立一個size = que.size()記錄每一層數量
- while回圈 size--
- 暫時節點儲存que.front()
- que.pop();
- 左右節點加入到que
- count++;
- return count;
Code
遞迴代碼
class Solution {
public:
int getNodesCount(TreeNode* cur) {
if(cur == NULL) return 0;
int leftcount = getNodesCount(cur->left);
int rightcount = getNodesCount(cur->right);
return 1 + leftcount + rightcount;
}
int countNodes(TreeNode* root) {
return getNodesCount(root);
}
};
迭代代碼
class Solution {
public:
int countNodes(TreeNode* root) {
queue<TreeNode*> que;
int count = 0;
if(root != NULL) que.push(root);
while(!que.empty()) {
int size = que.size();
while(size--) {
TreeNode* node = que.front();
que.pop();
if(node->left)que.push(node->left);
if(node->right)que.push(node->right);
count++;
}
}
return count;
}
};
總結
自己实现过程中遇到哪些困难
今天卡住我的反而是在遞迴,對於傳入值以及單遞迴的思考不足,自己需要再對遞迴的部分進行了解
而在迭代上反而比較清晰,腦袋中有那個畫面存在,對於目前的我來說感覺迭代更加直觀一點
今日收获,记录一下自己的学习时长
今天因為有兩題昨天做過,所以整體大概花不到兩個小時就把題目做完了,但每天這樣做遞迴的題目,感覺自己對於二叉樹又有更深一點的理解了。
相關資料
详细布置
104.二叉树的最大深度
题目链接/文章讲解/视频讲解: https://programmercarl.com/0104.二叉树的最大深度.html
111.二叉树的最小深度
题目链接/文章讲解/视频讲解:https://programmercarl.com/0111.二叉树的最小深度.html
222.完全二叉树的节点个数
题目链接/文章讲解/视频讲解:https://programmercarl.com/0222.完全二叉树的节点个数.html