目录
嵌入式学习分享个人主页：Orion嵌入式随想录 - 小红书 (xiaohongshu.com)
广度优先
-
解题思路
-
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
-
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。这种层序遍历方式就是图论中的广度优先遍历，应用在二叉树上。
-
-
解题步骤
-
定义队列，增加节点
-
定义结果数组
-
开启循环，定义长度和存放数组，队列不为空则按照队列长度存储遍历节点
-
存入一组结果
-
-
代码注意
-
root != NULL放入头节点 -
vector<int> vec;在for前定义
-
-
代码一：层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
// 递归法
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth)
{
if (cur == nullptr) return;
if (result.size() == depth) result.push_back(vector<int>());
result[depth].push_back(cur->val);
order(cur->left, result, depth + 1);
order(cur->right, result, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
return result;
}
};226.翻转二叉树
-
文章讲解：代码随想录
-
注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果。
-
这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次。
-
层序遍历依然可以的，只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的。
递归法 ⭐
-
解题思路
-
确定递归函数的参数和返回值：参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为
TreeNode*。 -
TreeNode* invertTree(TreeNode* root) -
确定终止条件：当前节点为空的时候，就返回。
-
if (root == NULL) return root; -
确定单层递归的逻辑：先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。
-
swap(root->left, root->right); invertTree(root->left); invertTree(root->right);
-
-
代码一：前序遍历递归
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
swap(root->left, root->right); // 中
invertTree(root->left); // 左
invertTree(root->right); // 右
return root;
}
};-
代码二：后序遍历递归
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
invertTree(root->left); // 左
invertTree(root->right); // 右
swap(root->left, root->right); // 中
return root;
}
};-
代码三：中序遍历递归
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
invertTree(root->left); // 左
swap(root->left, root->right); // 中
invertTree(root->left); // 右 不是严格的右
return root;
}
};迭代法
-
代码一：前序遍历迭代
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
swap(node->left, node->right);
if(node->right) st.push(node->right); // 右
if(node->left) st.push(node->left); // 左
}
return root;
}
};-
代码二：前序统一迭代
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> st;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
st.push(node); // 中
st.push(NULL);
} else {
st.pop();
node = st.top();
st.pop();
swap(node->left, node->right); // 节点处理逻辑
}
}
return root;
}
};层序法
-
代码一：层序遍历
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
swap(node->left, node->right); // 节点处理
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return root;
}
};101.对称二叉树
后序遍历法 ⭐
-
解题思路
-
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
-
比较：比较的是两个子树的里侧和外侧的元素是否相等。
-
遍历：本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值（处理完左右返回中处理）来判断两个子树的内侧节点和外侧节点是否相等。正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。
-
-
解题步骤
-
确定递归函数的参数和返回值：因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数是左子树节点和右子树节点。返回值是bool类型。
- 确定终止条件：要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
-
节点为空的情况有：（注意比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
-
左右都为空，对称，返回true
-
左不为空，右为空，不对称 return false
-
左节点为空，右节点不为空，不对称，return false
-
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
-
左右都不为空，比较节点数值，不相同就return false
-
-
剩下的就是 左右节点都不为空，且数值相同的情况。进入下一步骤。
-
-
确定单层递归的逻辑：此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
-
比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
-
比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
-
如果左右都对称就返回true ，有一侧不对称就返回false 。
-
-
-
代码一：后序递归
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
// 首先排除空节点的情况
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
// 排除了空节点，再排除数值不相同的情况
else if (left->val != right->val) return false;
// 此时就是：左右节点都不为空，且数值相同的情况
// 此时才做递归，做下一层的判断
bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left); // 左子树：右、 右子树：左
bool isSame = outside && inside; // 左子树：中、 右子树：中 （逻辑处理）
return isSame;
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}
};-
代码二：后序递归简洁版
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
else return compare(left->left, right->right) && compare(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}
};迭代法
-
解题思路
-
这道题目也可以使用迭代法，但要注意，这里的迭代法不是前中后序的迭代写法，因为本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了。
-
这里我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（注意这不是层序遍历）
-
-
代码一：迭代法队列
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
queue<TreeNode*> que;
que.push(root->left); // 将左子树头结点加入队列
que.push(root->right); // 将右子树头结点加入队列
while (!que.empty()) { // 接下来就要判断这两个树是否相互翻转
TreeNode* leftNode = que.front(); que.pop();
TreeNode* rightNode = que.front(); que.pop();
if (!leftNode && !rightNode) { // 左节点为空、右节点为空，此时说明是对称的
continue;
}
// 左右一个节点不为空，或者都不为空但数值不相同，返回false
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
que.push(leftNode->left); // 加入左节点左孩子
que.push(rightNode->right); // 加入右节点右孩子
que.push(leftNode->right); // 加入左节点右孩子
que.push(rightNode->left); // 加入右节点左孩子
}
return true;
}
};-
代码二：迭代法栈：
-
迭代法，其实是把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较，那么其实使用栈也是可以的。只要把队列原封不动的改成栈就可以。
-
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
stack<TreeNode*> st; // 这里改成了栈
st.push(root->left);
st.push(root->right);
while (!st.empty()) {
TreeNode* leftNode = st.top(); st.pop();
TreeNode* rightNode = st.top(); st.pop();
if (!leftNode && !rightNode) {
continue;
}
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
st.push(leftNode->left);
st.push(rightNode->right);
st.push(leftNode->right);
st.push(rightNode->left);
}
return true;
}
};（说明：基于代码随想录课程学习，部分内容引用代码随想录文章）
标签：right,return,层序,Part2,二叉树,TreeNode,root,节点,left From： https://blog.csdn.net/qq_48896570/article/details/139125732