226.翻转二叉树
初印象: 感觉层序遍历一遍再倒过来就好了...
思路
实际上只要遍历每个节点并反转其左右孩子就可以了，因此用其他遍历方法都能做，除了递归法的中序遍历做不了，因为递归法的中序遍历会将某些节点的左右孩子翻转两次（按照左中右的顺序的话，先判断左，翻转，在判断右，这样的话此时的右就是刚刚被翻转过来的左）。
递归法
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) {
stack<TreeNode *> st;
if (root) {
st.push(root);
}
while (!st.empty()) {
TreeNode *cur = st.top();
st.pop();
swap(cur->left, cur->right);
if (cur->right) {
st.push(cur->right);
}
if (cur->left) {
st.push(cur->left);
}
}
return root;
}
};
101.对称二叉树
递归法
-
参数和返回值:
比较的是左右子树，返回值是布尔类型 -
终止条件
- 左右一个为空一个不为空->false
- 左右都不为空但是值不相等->false
- 左右都为空->true
-
每层逻辑:
比较outside和inside，只要出现了左右不相等的情况，递归立马停止，返回值。如果递归到左右子树都是空的时候，那也就是遍历完了，就返回true。 -
后序遍历（不是严格的后序遍历）
class Solution {
public:
bool isEqual(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 = isEqual(left->left, right->right);
bool inSide = isEqual(left->right, right->left);
bool equal = outSide && inSide;
return equal;
}
bool isSymmetric(TreeNode *root) {
if (root == NULL) {
return false;
}
return isEqual(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 isEqual(TreeNode *cur) {
//初始化
stack<TreeNode *> st;
st.push(cur->right);
st.push(cur->left);
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(rightNode->right);
st.push(leftNode->left);
st.push(rightNode->left);
st.push(leftNode->right);
}
return true;
}
bool isSymmetric(TreeNode *root) {
if (root == NULL) {
return false;
}
return isEqual(root);
}
};
104.二叉树的最大深度
递归法
本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。因为前序是先处理的是深度，所以进入下一个节点的时候首先加深度，也就是从上往下。而后序是先遍历完左右子树，到了底部达成递归终止条件，再通过递归增加高度，是从下往上的增加高度。
高度和深度是相反的表示，深度是从上到下数的，而高度是从下往上数。所以树的深度和高度是相等的，而对其他节点来说深度和高度不一定相等。
-
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
-
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
-
后序遍历
实际上就是先让左边搜索到最底层，再让右边搜索到最底层，然后再再递归函数栈归的过程中不断的增加高度。比较哪个高度高。
class Solution {
public:
int maxDepth(TreeNode *root) {
if (!root) {
return 0;
}
int left = maxDepth(root->left);
int right = maxDepth(root->right);
int depth = 1+max(left, right);
return depth;
}
};
-
前序遍历（深度回溯）
先遍历左子树到最深，然后再回溯遍历上一个节点的右子树，如果没有就接着回溯。这里更新节点到上一个回溯点（实际上并没有主动更新，而是通过函数调用自动更新的）是通过递归栈归来实现的，可以想像递归是一系列盒子，当前盒子里就保存着当前节点，当最下面的盒子被释放的时候（递归达到终止），就返回到上一个盒子里了，而上一个盒子里装的是之前存放在盒子里的节点。也就是stack frame里面的东西。
-
来自claude3.5的解释
"盒子"实际上就是我们在计算机科学中称为"栈帧"（Stack Frame）的概念。每次函数调用都会在调用栈上创建一个新的栈帧。我们可以把这个过程想象成这样：-
盒子（栈帧）的内容：
每个"盒子"（栈帧）里不仅存放当前节点的信息，还包括：- 局部变量（如当前的 depth 值）
- 函数参数
- 返回地址（告诉程序当前函数执行完毕后应该返回到哪里）
-
递归过程：
- 每次递归调用 getdepth 函数时，都会在调用栈上放置一个新的"盒子"（创建新的栈帧）。
- 这个新"盒子"位于前一个"盒子"的上面。
- 每个"盒子"都保存了其对应节点的信息和当前的 depth 值。
-
回溯过程：
- 当递归达到终止条件（如遇到叶节点），最上面的"盒子"完成其任务。
- 这个"盒子"被移除（栈帧被弹出），控制权返回到下面的"盒子"。
- 返回过程中，程序自动恢复到下面"盒子"所保存的状态，包括节点信息和其他局部变量。
-
深度调整：
- 代码中的 depth-- 操作确保了当我们回到上一层"盒子"时，深度值与当前节点位置保持一致。
- 这不改变节点，而是调整与节点关联的深度计数。
-
整体视角：
- 整个递归过程可以看作是在调用栈上"盒子"的不断堆叠和移除。
- 每个"盒子"代表树中的一个节点和其状态。
- "盒子"的堆叠对应树的深度优先遍历。
- "盒子"的移除对应从深层节点回溯到浅层节点。
-
优势：
- 这种机制允许程序在遍历树时保持每个节点的上下文信息。
- 回溯变得简单，因为前一个节点的所有信息都保存在它的"盒子"（栈帧）中。
-
class Solution {
public:
int result;
void getdepth(TreeNode* node, int depth) {
result = depth > result ? depth : result; // 中
if (node->left == NULL && node->right == NULL) return ;
if (node->left) { // 左
depth++; // 深度+1
getdepth(node->left, depth);
depth--; // 回溯，深度-1
}
if (node->right) { // 右
depth++; // 深度+1
getdepth(node->right, depth);
depth--; // 回溯，深度-1
}
return ;
}
int maxDepth(TreeNode* root) {
result = 0;
if (root == NULL) return result;
getdepth(root, 1);
return result;
}
};
迭代法
层序遍历在之前二叉树Part01写过了，这里不放代码了
111.二叉树的最小深度
递归法
- 后序遍历(高度)
class Solution {
public:
int getDepth(TreeNode* node) {
if (node == NULL) return 0;
int leftDepth = getDepth(node->left); // 左
int rightDepth = getDepth(node->right); // 右
// 中
// 当一个左子树为空，右不为空，这时并不是最低点
if (node->left == NULL && node->right != NULL) {
return 1 + rightDepth;
}
// 当一个右子树为空，左不为空，这时并不是最低点
if (node->left != NULL && node->right == NULL) {
return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
};
- 前序遍历(深度)
class Solution {
private:
int result;
void getdepth(TreeNode* node, int depth) {
// 函数递归终止条件
if (node == nullptr) {
return;
}
// 中，处理逻辑：判断是不是叶子结点
if (node -> left == nullptr && node->right == nullptr) {
result = min(result, depth);
}
if (node->left) { // 左
getdepth(node->left, depth + 1);
}
if (node->right) { // 右
getdepth(node->right, depth + 1);
}
return ;
}
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
result = INT_MAX;
getdepth(root, 1);
return result;
}
};
迭代法
二叉树Part01写过了，不再赘述
