摘要
- 二叉樹的遞歸遍歷對(duì)應(yīng)著DFS买决，二叉樹的層序遍歷對(duì)應(yīng)著BFS
- 層序遍歷的迭代法實(shí)現(xiàn)一般用隊(duì)列進(jìn)行實(shí)現(xiàn)
LeetCode102 二叉樹的層序遍歷
- 這和教材上的層序遍歷有所不同沛婴，題目要求我們區(qū)分樹每一層吼畏。
- 樹的第
k層的節(jié)點(diǎn)數(shù)最多為個(gè)，不過層序遍歷并不是遍歷完全二叉樹嘁灯，所以每層的個(gè)數(shù)應(yīng)該由我們手動(dòng)控制泻蚊。
- 實(shí)現(xiàn)思路：
- 用
size記錄當(dāng)前層的節(jié)點(diǎn)個(gè)數(shù)，每從隊(duì)列中彈出一個(gè)當(dāng)前層的節(jié)點(diǎn)丑婿，size就減一性雄，當(dāng)size為零時(shí)，當(dāng)前層遍歷完成羹奉。
- 用
初見題目時(shí)完整的題解代碼如下
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) {
return res;
}
queue<TreeNode*> que;
que.push(root);
int size = que.size();
int level = 0;
res.push_back({});
while (!que.empty()) {
if (que.front()) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
res[level].push_back(que.front()->val);
}
que.pop();
size--;
if (size == 0 && !que.empty()) {
size = que.size();
level++;
res.push_back({});
}
}
return res;
}
};
看了講解之后秒旋，以上的方法雖然邏輯是對(duì)的，但是由于每次循環(huán)只處理一個(gè)節(jié)點(diǎn)诀拭，多了很多不必要的
size個(gè)數(shù)的判斷迁筛，所以還可以改良。可以在循環(huán)內(nèi)添加一個(gè)
for循環(huán)耕挨，每次循環(huán)直接遍歷完一層
完整的題解代碼如下
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root) {
que.push(root);
}
vector<vector<int>> res;
while (!que.empty()) {
int size = que.size();
vector<int> level;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
level.push_back(que.front()->val);
que.pop();
}
res.push_back(level);
}
return res;
}
};
LeetCode107 二叉樹的層序遍歷II
- 將上一題的答案數(shù)組反轉(zhuǎn)即可
- 有DFS的方法细卧，日后補(bǔ)充
完整的題解代碼如下
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> que;
if (root) {
que.push(root);
}
vector<vector<int>> res;
while (!que.empty()) {
int size = que.size();
vector<int> level;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
level.push_back(que.front()->val);
que.pop();
}
res.push_back(level);
}
reverse(res.begin(), res.end());
return res;
}
};
LeetCode199 二叉樹的右視圖
- 取每層的最后一個(gè)節(jié)點(diǎn)的值放入答案數(shù)組
完整的題解代碼如下
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> que;
if (root) {
que.push(root);
}
vector<int> res;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
if (i == size - 1) res.push_back(que.front()->val);
que.pop();
}
}
return res;
}
};
LeetCode637 二叉樹的層平均值
完整題解代碼如下
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
vector<double> res;
while (!que.empty()) {
int size = que.size();
double average = 0;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
average += que.front()->val;
que.pop();
}
average /= size;
res.push_back(average);
}
return res;
}
};
LeetCode429 N叉樹的層序遍歷
- 只需要修改每層遍歷的邏輯，將添加左孩子和右孩子進(jìn)隊(duì)列擴(kuò)展為添加N個(gè)孩子進(jìn)隊(duì)列
N叉樹的節(jié)點(diǎn)定義
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
完整題解代碼如下
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
queue<Node*> que;
if (root) que.push(root);
vector<vector<int>> res;
while (!que.empty()) {
int size = que.size();
vector<int> level;
for (int i = 0; i < size; i++) {
for (auto& iter : que.front()->children) {
if (iter) que.push(iter);
}
level.push_back(que.front()->val);
que.pop();
}
res.push_back(level);
}
return res;
}
};
LeetCode515 在每個(gè)樹行中找最大值
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
vector<int> res;
while (!que.empty()) {
int size = que.size();
int maxVal = INT_MIN;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
maxVal = maxVal > que.front()->val ? maxVal : que.front()->val;
que.pop();
}
res.push_back(maxVal);
}
return res;
}
};
LeetCode116 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針
116. 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針 - 力扣（Leetcode）
完整題解代碼如下
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if (root) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0;i < size; i++) {
Node* cur = que.front();
que.pop();
// 每層的最后一個(gè)節(jié)點(diǎn)的next為nullptr
Node* next = i == size - 1 ? nullptr : que.front();
cur->next = next;
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
}
return root;
}
};
LeetCode117 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針
117. 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針 II - 力扣（Leetcode）
- 由于116的題解其實(shí)已經(jīng)考慮了非完全二叉樹的情況筒占，所以題解代碼相同
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if (root) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0;i < size; i++) {
Node* cur = que.front();
que.pop();
// 每層的最后一個(gè)節(jié)點(diǎn)的next為nullptr
Node* next = i == size - 1 ? nullptr : que.front();
cur->next = next;
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
}
return root;
}
};
LeetCode104 二叉樹的最大深度
完整題解代碼如下
class Solution {
public:
int maxDepth(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
int res = 0;
while (!que.empty()) {
int size = que.size();
res++;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
}
return res;
}
};
LeetCode111 二叉樹的最小深度
- 根據(jù)最小深度的定義贪庙，當(dāng)遍歷到一個(gè)左右孩子都為空的節(jié)點(diǎn)時(shí)，即可直接返回當(dāng)前節(jié)點(diǎn)所在的層數(shù)
class Solution {
public:
int minDepth(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
int res = 0;
while (!que.empty()) {
int size = que.size();
res++;
for (int i = 0; i < size; i++) {
if (!que.front()->left && !que.front()->right) {
return res;
}
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
}
return res;
}
};
LeetCode226 翻轉(zhuǎn)二叉樹
怎么理解翻轉(zhuǎn)翰苫？翻轉(zhuǎn)后的二叉樹與原來的二叉樹是鏡面對(duì)稱的止邮，實(shí)際上就是交換每個(gè)節(jié)點(diǎn)的左孩子和右孩子。
- image.png
二叉樹的遍歷中奏窑，有前序导披、中序、后序良哲、層序四種方式盛卡，都能訪問到二叉樹的所有節(jié)點(diǎn)助隧。選擇哪一種呢筑凫？
在這道題目里，只有中序是不太合適的并村，或者說邏輯上會(huì)有陷阱巍实。先看前序遍歷，代碼如下
遞歸法哩牍，前序遍歷
class Solution {
public:
void invertTreeWorkPlace(TreeNode* cur) {
if (cur == nullptr) {
return;
}
swap(cur->left, cur->right);
invertTreeWorkPlace(cur->left);
invertTreeWorkPlace(cur->right);
}
TreeNode* invertTree(TreeNode* root) {
invertTreeWorkPlace(root);
return root;
}
};
那中序遍歷是不是把swap(cur->left, cur->right)下移一行就可以了呢棚潦？
class Solution {
public:
void invertTreeWorkPlace(TreeNode* cur) {
if (cur == nullptr) {
return;
}
invertTreeWorkPlace(cur->left);
swap(cur->left, cur->right); // 這合理嗎？
invertTreeWorkPlace(cur->right);
}
TreeNode* invertTree(TreeNode* root) {
invertTreeWorkPlace(root);
return root;
}
};
我們自己模擬一次遞歸的過程就知道問題出在哪了
- 以LeetCode的示例1為例膝昆，一直遞歸調(diào)用直到節(jié)點(diǎn)1丸边，
image.png
- 節(jié)點(diǎn)一為葉節(jié)點(diǎn)叠必，所以
invertTreeWorkPlace(cur->left)直接返回；swap(cur->left, cur->right)實(shí)踐上交換了兩個(gè)nullptr妹窖；invertTreeWorkPlace(cur->right)也直接返回 - 返回到節(jié)點(diǎn)2纬朝，節(jié)點(diǎn)2執(zhí)行
swap(cur->left, cur->right)
image.png
- 然后再執(zhí)行
invertTreeWorkPlace(cur->right)，問題就來了骄呼，這時(shí)候的右子樹是原來的左子樹共苛，實(shí)際上按這樣的代碼我們一直都在操作原來的二叉樹的左子樹。這就是中序遍歷在操作節(jié)點(diǎn)時(shí)的邏輯陷阱蜓萄。
一定要用中序遍歷的話隅茎，就要注意此時(shí)要操作原來右子樹就是要操作交換后的左子樹。
class Solution {
public:
void invertTreeWorkPlace(TreeNode* cur) {
if (cur == nullptr) {
return;
}
invertTreeWorkPlace(cur->left);
swap(cur->left, cur->right);
invertTreeWorkPlace(cur->left);
}
TreeNode* invertTree(TreeNode* root) {
invertTreeWorkPlace(root);
return root;
}
};
統(tǒng)一形式的迭代法實(shí)現(xiàn)嫉沽，用函數(shù)指針提高代碼復(fù)用
class Solution {
public:
static void preorder(TreeNode* cur, stack<TreeNode*>& st) {
st.pop();
if (cur->right) st.push(cur->right);
if (cur->left) st.push(cur->left);
st.push(cur);
st.push(nullptr);
}
static void swapLeftAndRight(TreeNode* cur) {
swap(cur->left, cur->right);
}
void treeTraversal(TreeNode* root,
void (*traversal)(TreeNode* cur, stack<TreeNode*>& st),
void (*handle)(TreeNode* cur))
{
stack<TreeNode*> st;
if (root) st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
if (cur) {
traversal(cur, st);
}
else {
st.pop();
cur = st.top();
st.pop();
handle(cur);
}
}
}
TreeNode* invertTree(TreeNode* root) {
treeTraversal(root, preorder, swapLeftAndRight);
return root;
}
};
LeetCode101 對(duì)稱二叉樹
- 這道題和 LeetCode226 類似辟犀，不過這里我們要做的是比較根節(jié)點(diǎn)的左右子樹是否鏡面對(duì)稱，所以要同時(shí)訪問兩棵樹耻蛇。
- 要先判斷當(dāng)前節(jié)點(diǎn)的左右子樹是否鏡面對(duì)稱踪蹬，所以采用后序遍歷的“左右中”，訪問完左右子樹后才能確定當(dāng)前節(jié)點(diǎn)是否為一個(gè)對(duì)稱二叉樹的根節(jié)點(diǎn)臣咖。
- 先采用遞歸法實(shí)現(xiàn)：
- 確定遞歸函數(shù)的參數(shù)和返回值：要比較左右子樹是否鏡面對(duì)稱跃捣，所以需要傳入左子樹和右子樹的根節(jié)點(diǎn)；比較結(jié)果有對(duì)稱和不對(duì)稱兩種夺蛇，為布爾值疚漆，所以返回類型為布爾值。
-
確定遞歸的終止條件：
- 左子樹為空刁赦，右子樹不為空娶聘；自然是不對(duì)稱的，返回false
- 左子樹不為空甚脉，右子樹為空丸升；同1
- 左右子樹都為空，說明這是一個(gè)葉節(jié)點(diǎn)牺氨，左右子樹都為空自然對(duì)稱狡耻，返回true
- 確定單層遞歸的邏輯：通過布爾運(yùn)算實(shí)現(xiàn)，首先判斷左子樹的左子樹是否和右子樹的右子樹相等猴凹；再判斷左子樹的右子樹是否和右子樹的左子樹相等夷狰；最后再判斷當(dāng)前節(jié)點(diǎn)的左孩子是否和右孩子相等。
遞歸法實(shí)現(xiàn)的完整代碼
class Solution {
public:
bool isSymmetricWorkPlace(TreeNode* left, TreeNode* right) {
if (!left && right) return false;
if (left && !right) return false;
if (!left && !right) return true;
bool res = true;
res = res && isSymmetricWorkPlace(left->left, right->right);
res = res && isSymmetricWorkPlace(left->right, right->left);
res = res && left->val == right->val;
return res;
}
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return isSymmetricWorkPlace(root->left, root->right);
}
};
- 另外可以通過迭代法來判斷樹的每層是否鏡面對(duì)稱郊霎，但要記得每層的
nullptr也要進(jìn)入隊(duì)列來在層序中區(qū)分左孩子和右孩子 - 注意沼头，每次比較的不是某個(gè)節(jié)點(diǎn)的左孩子和右孩子，而是某層的最左未被比較的節(jié)點(diǎn)和最右未被比較的節(jié)點(diǎn)。
以LeetCode的示例1為例
- 首先比較隊(duì)列頭和隊(duì)列尾进倍，此時(shí)的隊(duì)列
[2, 2]
image.png
- 然后隊(duì)列頭和隊(duì)列尾都出隊(duì)土至。按鏡面對(duì)稱讓隊(duì)列頭的左孩子、右孩子和隊(duì)列尾的左孩子猾昆、孩子入隊(duì)毙籽，此時(shí)的隊(duì)列
[3, 4, 4, 3]
image.png
- 繼續(xù)上述步驟，隊(duì)列頭和隊(duì)列尾出隊(duì)毡庆，二者左右孩子按鏡面對(duì)稱入隊(duì)
- 此時(shí)隊(duì)列
[nullptr, nullptr, 4, 4, nullptr, nullptr]
- 此時(shí)隊(duì)列
- 循環(huán)直至隊(duì)列為空坑赡，注意這不是層序遍歷，并不是比較完一層再到下一層么抗。
采用雙端隊(duì)列迭代法來實(shí)現(xiàn)判斷二叉樹是否對(duì)稱
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root) {
deque<TreeNode*> deq;
deq.push_front(root->left);
deq.push_back(root->right);
while (!deq.empty()) {
TreeNode* left = deq.front();
deq.pop_front();
TreeNode* right = deq.back();
deq.pop_back();
// 左右子樹都為空自然是對(duì)稱的
if (!left && !right) {
continue;
}
// 這里是短路判斷毅否，只有要比較的左右兩個(gè)節(jié)點(diǎn)都不為空才會(huì)比較值，防止操作空指針
if (!left || !right || (left->val != right->val)) {
return false;
}
// 用雙端隊(duì)列更加直觀的體現(xiàn)出對(duì)稱蝇刀，其實(shí)也可以用普通隊(duì)列實(shí)現(xiàn)
deq.push_front(left->right);
deq.push_front(left->left);
deq.push_back(right->left);
deq.push_back(right->right);
}
}
return true;
}
};
- 那用真正的層序遍歷是否可以做這道題呢螟加？當(dāng)然是可以的，同樣也要注意往每層的序列中加入
nullptr來區(qū)分左孩子和右孩子吞琐。 - 但是層序遍歷有一個(gè)問題捆探，就是我們要遍歷完這一層后才能判斷當(dāng)前層是否鏡面對(duì)稱，相當(dāng)于要多花一倍的時(shí)間站粟。為了便于對(duì)比黍图，在這里還是給出用層序遍歷的實(shí)現(xiàn)代碼。
層序遍歷的實(shí)現(xiàn)代碼
class Solution {
public:
bool isSymmetric(TreeNode* root) {
bool res = true;
if (!root) return res;
queue<TreeNode*> que;
if (root) que.push(root);
while (!que.empty()) {
int size = que.size();
vector<TreeNode*> level;
for (int i = 0; i < size; i++) {
if (que.front()) {
que.push(que.front()->left);
que.push(que.front()->right);
}
level.push_back(que.front());
que.pop();
}
if (level.size() > 1 && level.size() % 2) return false;
for (int i = 0, j = level.size() - 1; i < j; i++, j--) {
if (!level[i] && !level[j]) continue;
if (!level[i] || !level[j] || level[i]->val != level[j]->val) {
return false;
}
}
}
return res;
}
};
