思路stack1 作为输入栈，实现在队列尾部插入整数(push)stack2 作为输出栈，实现在队列头部删除整数(pop)pop时，需要根据stack2的状态进行操作。如果当前栈为空，需要将栈1中的所有元素放入栈2，实现顺序的反转；如果当前栈2非空，则直接读取栈顶元素，将其弹出栈的常见基本操作操作名称英文常用名称功能描述时间复杂度是否改变栈结构入栈push / push_back将元素添加到栈顶O(1)是出栈pop移除并返回栈顶元素O(1)是获取栈顶元素top / peek查看（不移除）栈顶元素O(1)否判断栈是否为空empty / isEmpty判断栈中是否没有元素O(1)否获取栈中元素个数...

先重建树，再层序遍历取最右重建二叉树：哈希表存储中序+递归二叉树的层序遍历：队列广度优先遍历访问二维数组的最后一行可以采用 arr[i].back() 语句，可以自动访问最后一个元素 #include <queue> #include <unordered_map> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 求二叉树的右视图 * @param preOrder int整型vector 先序遍历 * @param inOrd...

前序（根左右）：第一个一定是根中序（左根右）：由前序的根划分为左右两个子树新建哈希表，递归构建左右子树步骤：如果前序或者中序为空，返回 nullptr取前序遍历的第一个值为根 rootVal在中序遍历中找到第一个 rootVal 的位置 idx，那么左边 [vin_left,idx-1] 是左子树的中序，右边 [idx+1,vin_right] 是右子树的中序记录左子树的长度 leftSize 来确定每次递归的区间 leftSize=idx-vin_left; 那么左子树的前序是 [preL+1, preL+leftSize]; 右子树的前序为 [preL+leftSize+1,preR]左子...

如果当前节点是o1或者o2，就直接返回当前节点分别递归查找左右子树如果左子树和右子树分别找到一个，那么当前节点就是公共祖先如果只在左子树中找到，就返回左子树的结果；右子树同理 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接...

思路：如果p和q都小于当前节点的val值，说明公共祖先在左子树，就去左子树找；都大于说明在右子树p 和 q 分居当前节点的左右两边（或者其中一个就是当前节点）→ 当前节点就是它们的最近公共祖先！直接返回当前节点的值 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名...

思路：设置一个辅助函数，平衡时直接返回子树的高度，不平衡时返回-1，主函数检查返回值是否为-1步骤：如果为空，返回值为0；递归计算左子树的高度（int left=checkHeight(root->left)），如果左子树返回值为-1，直接返回-1；递归计算右子树，同理左子树计算左右子树的高度差，如果大于1，也return -1；知识点：求整型数据的绝对值：abs() 方法在C语言中，只对int整型生效，作用是正确答案： /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right...

思路：根据层序遍历的思想使用队列，设置标志位leaf用来表示是否进入最后一层缺口阶段。leaf==true意思为现在已经进入最后一层缺口阶段，任何结点都不能有孩子。步骤：如果根结点为空，为完全二叉树，直接返回true初始化队列存入头结点【queue<TreeNode*> q; q.push(root)】设置leaf初始值为false，表示没有进入最后一层只要队列非空，遍历每个节点时：如果节点有右孩子但无左孩子 → 直接返回 false（违反完全二叉树性质）。如果节点不双全（只有左孩子 或 无孩子），则置 leaf = true（表示已进入最后一层缺口阶段）。如果 leaf == t...

一 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ vo...

std::swap（或手动用临时变量交换）在处理指针时，对空指针（nullptr）完全安全，它会正确处理所有情况，包括左右子树有一个或两个都为空。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * *...

思路：递归分别合并左子树和右子树，建立在t1的基础上，最后返回t1.基本条件t1为空，直接返回t2【在合并二叉树时，当 t1 为 nullptr（为空），不是“将 t2->val 赋值给 t1”或其他类似操作？——t1 根本就不存在任何节点，不可能去进行任何操作】t2为空，直接返回t1，因为这个步骤在第一步之后，所以t1肯定不为空。都不为空，则两者值相加递归语句递归合并左子树，t1->left=mergeTrees(t1->left, t2->left)：需要赋值回去；右子树同理：t1->right = mergeTrees(t1->right, t2-&g...

首先明确：中序遍历回文不能用来判断二叉树对称思路：写一个函数，回答这个问题：“以节点A为根的子树”和“以节点B为根的子树”是不是互为镜像？=》isMirror(TreeNode* A, TreeNode* B)1A 和 B 都为空（nullptr）true（两个空树当然对称）2A 和 B 有一个为空，另一个不空false（一边有树一边没树，不对称）3A 和 B 都不空，但 A->val != B->valfalse（根值都不一样，肯定不对称）4A 和 B 都不空，且值相等继续检查： 1. A的左子树 和 B的右子树 是否镜像 2. A的右子树 和 B的左子树 是否镜像 只有这两对都...

中序遍历 + 维护“上一个节点”指针思路根据二叉树的中序遍历思想进行处理处理时连接链表，用prev记录访问过的上一个值进行连接步骤初始化prev和head为空，进行中序遍历访问每个节点，如果节点为空return维护一个prev始终指向当前访问的上一个节点（已经处理好的双向链表的最后一个节点）处理当前访问的节点：如果访问时prev为空，说明这是第一个节点，让head=node; 然后prev=node;保存当前节点如果prev非空，就连接节点prev->right=node; node->left=prev;为双向链表；然后prev后移：prev=node;正确答案 /* struc...

递归判断左右子树思路两种基本情况：判断树是否为空，为空直接返回判断树是否有左右孩子，都没有判断根结点值是否为sum递归情况：当前结点为非叶结点，进行递归每次都判断左子树值是否加和为sum-root->val;（递归）每次都判断左子树值是否加和为sum-root->val;（递归）正确答案 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * ...

每层访问完根据条件reverse思路根据层次遍历思想，设置队列，同时设置一个布尔变量判断这个数组是否进行元素反转布尔变量可以实现两个值来回变化，每层存储后，都对其进行取非操作知识点反转函数reverse用法：reverse(v.begin(), v.end())反转整个容器vectorreverse(v.begin()+i, v.begin()+j)反转部分区间 [i, j)reverse(v.begin(), v.begin()+3); // 只反转前三个 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct...