1、解题思路前序遍历：根节点 -> 左子树 -> 右子树。中序遍历：左子树 -> 根节点 -> 右子树。重建步骤：前序遍历的第一个元素是根节点。在中序遍历中找到根节点的位置，左侧是左子树，右侧是右子树。递归构建左子树和右子树。2、代码实现C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include &...

1、解题思路层序遍历（BFS）序列化：使用队列进行层序遍历。节点值之间用逗号分隔，空节点用 # 表示。层序遍历反序列化：将字符串按逗号分割成节点列表。使用队列重建二叉树，依次处理每个节点。2、代码实现C++ /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ #include <sstream> #include <string> #include &...

1、解题思路递归遍历： 从根节点开始递归遍历二叉树。如果当前节点是 o1 或 o2，则返回当前节点。否则，递归遍历左子树和右子树。如果左右子树都返回非空节点，则当前节点是LCA。如果只有一个子树返回非空节点，则返回该节点。复杂度分析： 时间复杂度：O(n)，每个节点最多访问一次。空间复杂度：O(h)，递归栈的深度为树的高度 h。2、代码实现C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullpt...

1、解题思路BST的性质：左子树的所有节点值小于当前节点值。右子树的所有节点值大于当前节点值。LCA的性质：如果 p 和 q 分别位于当前节点的左右子树中，则当前节点就是它们的LCA。如果 p 或 q 等于当前节点，则当前节点就是它们的LCA。如果 p 和 q 都小于当前节点值，则LCA在左子树中。如果 p 和 q 都大于当前节点值，则LCA在右子树中。递归方法：根据BST的性质递归搜索LCA。迭代方法：使用循环代替递归，降低空间复杂度。2、代码实现C++（递归） /** * struct TreeNode { * int val; * struct TreeNode *left; * str...

1、解题思路自底向上的递归：从叶子节点开始计算每个节点的高度。在计算高度的同时，检查左右子树的高度差是否超过1。如果超过1，则直接返回不平衡的结果，避免重复计算。复杂度优化：传统自顶向下递归会重复计算子树高度，时间复杂度为 O(n^2)。自底向上递归只需计算一次树高，时间复杂度为 O(n)。2、代码实现C++（自底向上递归） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(n...

1、解题思路层序遍历（BFS）：使用队列进行层序遍历。检查是否存在某个节点为空后，后面还有非空节点。标记法：在层序遍历时，标记第一次遇到空节点的情况。如果在标记后还遇到非空节点，则不是完全二叉树。2、代码实现C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <queue> class Solution...

1、解题思路递归方法（中序遍历验证）： 二叉搜索树的中序遍历结果是一个严格递增的序列。进行中序遍历，记录前一个节点的值，确保当前节点的值大于前一个节点的值。递归方法（上下界验证）： 每个节点都有一个值的上下界限制。左子树的所有节点值必须小于当前节点值（上界为当前节点值）。右子树的所有节点值必须大于当前节点值（下界为当前节点值）。迭代方法（中序遍历）： 使用栈模拟中序遍历。检查遍历结果是否严格递增。2、代码实现C++（中序遍历递归） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *rig...

1、解题思路递归方法：从根节点开始，递归交换每个节点的左右子树。递归终止条件是当前节点为空。迭代方法（BFS或DFS）：使用栈或队列遍历二叉树。每次取出一个节点，交换其左右子树。将子节点加入栈或队列继续处理。2、代码实现C++（递归） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /*...

1、解题思路递归方法：从两棵树的根节点开始递归合并。如果两个节点都存在，创建一个新节点，值为两节点值之和。递归合并左子树和右子树。如果其中一个节点为空，直接返回另一个节点。迭代方法（BFS或DFS）：使用队列或栈同时遍历两棵树。每次取出两个树的对应节点，按照规则合并。将合并后的节点的子节点加入队列或栈继续处理。2、代码实现C++（递归） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), r...

1、解题思路递归方法：对称二叉树的条件是：左子树和右子树互为镜像。两个子树互为镜像的条件： 它们的根节点值相同。左子树的左子树与右子树的右子树互为镜像。左子树的右子树与右子树的左子树互为镜像。迭代方法（BFS或DFS）：使用队列或栈进行层次遍历或深度遍历。每次比较两个节点（左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点）。如果所有节点都满足对称条件，则二叉树对称。2、代码实现C++（递归） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNod...

1、解题思路中序遍历：二叉搜索树的中序遍历结果是升序的，因此可以通过中序遍历来调整指针。使用递归或迭代方法进行中序遍历，同时记录前驱节点 prev，并在遍历过程中调整指针。指针调整：遍历过程中，当前节点的 left 指针指向 prev。prev 的 right 指针指向当前节点（如果 prev 不为空）。更新 prev 为当前节点。头节点处理：链表的最左节点（最小值）即为双向链表的头节点，可以通过遍历找到最左节点。2、代码实现C++（递归） /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; ...

1、解题思路递归方法：从根节点开始递归遍历二叉树。每遍历到一个节点，将 sum 减去当前节点的值。如果当前节点是叶子节点且剩余 sum 为0，则返回 true。否则，递归检查左子树和右子树是否存在满足条件的路径。迭代方法（DFS或BFS）：使用栈（DFS）或队列（BFS）进行遍历，同时记录路径的当前和。遇到叶子节点时，检查路径和是否等于 sum。2、代码实现C++（递归） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x)...

1、解题思路递归方法： 二叉树的最大深度等于其左子树和右子树的最大深度中的较大者加1。递归终止条件是当前节点为空，此时深度为0。迭代方法（层次遍历）： 使用队列进行层次遍历，每次遍历一层，深度加1，直到队列为空。2、代码实现C++（递归） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: ...

1、解题思路之字形层序遍历可以通过层序遍历的变种来实现：仍然使用队列进行层序遍历。根据当前层数的奇偶性决定遍历方向： 奇数层（如第1层）从左到右遍历。偶数层（如第2层）从右到左遍历。可以通过反转当前层的列表或使用双端队列来控制遍历方向。2、代码实现C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <thre...