行业知识
代码随想录算法训练营第十六天|654.最大二叉树，167.合并二叉树，700.二叉搜索树中的搜索
2026-11-05 07:02:43
来源：互联网转载
��654.最大二叉树
167.合并二叉树
700.二叉搜索树中的搜索
654.最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为 nums 中的最大值。
- 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
C++
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: TreeNode* constructMaximumBinaryTree(vector& nums) { TreeNode* node = new TreeNode(0); if (nums.size() == 1) { node->val = nums[0]; return node; } // 找到数组中最大的值和对应的下标 int maxValue = 0; int maxValueIndex = 0; for (int i = 0; i maxValue) { maxValue = nums[i]; maxValueIndex = i; } } node->val = maxValue; // 最大值所在的下标左区间 构造左子树 if (maxValueIndex > 0) { vector newVec(nums.begin(), nums.begin() + maxValueIndex); node->left = constructMaximumBinaryTree(newVec); } // 最大值所在的下标右区间 构造右子树 if (maxValueIndex right = constructMaximumBinaryTree(newVec); } return node; }}; 优化
使用了辅助函数constructMaximumBinaryTree来接收数组的起始和终止索引，从而避免创建新的子数组：
- 辅助函数使用索引：通过为constructMaximumBinaryTree函数添加两个额外的参数start和end，我们可以直接在原数组上操作，而不需要每次都创建新的数组或子数组。这样，我们只需在原始数组上改变索引的范围来表示不同的子数组。
- 避免额外的数组拷贝：原始代码中通过创建新的vector实例来构造左右子树，这不仅增加了内存使用，还增加了运行时间。优化后的代码直接在原数组上通过索引操作，避免了这种额外开销。
- 递归逻辑保持不变：优化后的代码仍然遵循找到最大值并以此构造根节点，然后递归地构造左右子树的逻辑。
性能分析
- 时间复杂度：O(n^2)，在最坏的情况下（数组每次都是升序或降序），每次找最大值需要O(n)，总共需要递归n次。
- 空间复杂度：O(n)，主要是由于递归调用栈的深度。尽管避免了额外的数组拷贝，但是在构造树时仍然需要为每个节点分配空间。对于平衡的二叉树，递归调用栈的深度是O(log n)，但是在最坏的情况下（形成链表），深度是O(n)。
#include using namespace std;struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution {public: // 辅助函数，使用数组索引避免额外的数组拷贝 TreeNode* constructMaximumBinaryTree(vector& nums, int start, int end) { if (start > end) return nullptr; // 递归的终止条件 // 找到数组中最大值的索引 int maxValueIndex = start; for (int i = start + 1; i nums[maxValueIndex]) { maxValueIndex = i; } } TreeNode* node = new TreeNode(nums[maxValueIndex]); // 递归构造左右子树 node->left = constructMaximumBinaryTree(nums, start, maxValueIndex - 1); node->right = constructMaximumBinaryTree(nums, maxValueIndex + 1, end); return node; } TreeNode* constructMaximumBinaryTree(vector& nums) { return constructMaximumBinaryTree(nums, 0, nums.size() - 1); }};python
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def constructMaximumBinaryTree(self, nums) -> TreeNode: return self.build(nums, 0, len(nums)) def build(self, nums, start, end): if start == end: return None # 找到最大值及其索引 max_val = max(nums[start:end]) max_index = nums.index(max_val, start, end) # 创建当前节点 node = TreeNode(max_val) node.left = self.build(nums, start, max_index) node.right = self.build(nums, max_index + 1, end) return node
167.合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
C++
这种合并树的方法直接在root1上进行修改，因此不需要额外的空间来创建合并后的树（除了递归调用栈占用的空间）。这种就地修改的方法效率较高，但它改变了root1的结构和数值，所以如果原始的root1树还需要保持不变，那么这种方法就不适用。
性能分析
- 时间复杂度：O(n)，其中n是两棵树中节点数较小的那棵树的节点数。每个节点最多被访问一次。
- 空间复杂度：O(h)，其中h是两棵树中较深的那棵树的高度，空间复杂度主要由递归调用栈的深度决定。在最坏的情况下，树完全不平衡，空间复杂度为O(n)；在最好的情况下，树完全平衡，空间复杂度为O(log n)。
C++
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if (root1 == NULL) return root2; // 如果t1为空，合并之后就应该是t2 if (root2 == NULL) return root1; // 如果t2为空，合并之后就应该是t1 // 修改了t1的数值和结构 root1->val += root2->val; // 中 root1->left = mergeTrees(root1->left, root2->left); // 左 root1->right = mergeTrees(root1->right, root2->right); // 右 return root1; }};方法二：
- 基本情况：如果root1和root2都是nullptr，则返回nullptr作为合并后的节点，表示在这个位置上没有节点。
- 节点值计算：如果root1或root2中的一个为空，那么合并后节点的值就是另一个非空节点的值；如果都非空，合并后节点的值是两个节点值的和。创建一个新的TreeNode作为合并后的节点。
- 递归合并子树：递归地合并root1和root2的左子树，然后合并它们的右子树。如果root1或root2中的一个为nullptr，递归时传递nullptr表示该方向上没有子树。
- 返回新树的根节点：最终返回新创建的节点newNode，它代表了合并后的二叉树的根节点。
性能分析
- 时间复杂度：O(n)，其中n是两棵树中节点数较少的那棵树的节点数。每个节点最多被访问一次，以计算新节点的值和递归合并其子树。
- 空间复杂度：O(n)，新树的创建导致了额外的空间开销，其中n是两棵树中节点数较多的那棵树的节点数。此外，递归调用栈的深度也会占用空间，对于平衡二叉树，空间复杂度是O(log n)；对于完全不平衡的二叉树，空间复杂度是O(n)。
这种实现方法保留了原始数据的不变性，适用于不希望修改原始输入树的场景。
C++
#include struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution {public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { // 如果两个节点都为空，则合并后的节点也为空 if (!root1 && !root2) { return nullptr; } // 计算合并后节点的值 int val = (root1 ? root1->val : 0) + (root2 ? root2->val : 0); TreeNode* newNode = new TreeNode(val); // 递归地合并左子树和右子树 newNode->left = mergeTrees(root1 ? root1->left : nullptr, root2 ? root2->left : nullptr); newNode->right = mergeTrees(root1 ? root1->right : nullptr, root2 ? root2->right : nullptr); return newNode; }};python
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode: # 如果两个节点都为空，则合并后的节点也为空 if not root1 and not root2: return None # 如果其中一个节点为空，合并后的节点就是另一个非空节点 # 注意这里使用了三元表达式，若root1为空，则使用root2的值，反之亦然 val = (root1.val if root1 else 0) + (root2.val if root2 else 0) newNode = TreeNode(val) # 递归地合并左子树和右子树 newNode.left = self.mergeTrees(root1.left if root1 else None, root2.left if root2 else None) newNode.right = self.mergeTrees(root1.right if root1 else None, root2.right if root2 else None) return newNode
700.二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
示例 1:
输入：root = [4,2,7,1,3], val = 2输出：[2,1,3]
示例 2:
输入：root = [4,2,7,1,3], val = 5输出：[]
递归法：
C++
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: TreeNode* searchBST(TreeNode* root, int val) { if (root == NULL || root->val == val) return root; TreeNode* result = NULL; if (root->val > val) result = searchBST(root->left, val); if (root->val right, val); return result; }};python
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def searchBST(self, root: TreeNode, val: int) -> TreeNode: if not root or root.val == val: return root # 如果当前节点的值大于要查找的值，递归搜索左子树 if root.val > val: return self.searchBST(root.left, val) # 如果当前节点的值小于要查找的值，递归搜索右子树 if root.val
迭代法：
迭代法相比递归法在空间复杂度上有优势，特别是在处理深度很大的二叉搜索树时，可以避免递归调用栈溢出的风险。
C++
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution {public: TreeNode* searchBST(TreeNode* root, int val) { while (root != nullptr && root->val != val) { // 根据二叉搜索树的性质选择向左或向右搜索 root = (root->val > val) ? root->left : root->right; } return root; // 返回找到的节点，如果没有找到则为nullptr }};python
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def searchBST(self, root: TreeNode, val: int) -> TreeNode: while root and root.val != val: # 根据二叉搜索树的性质选择向左或向右搜索 root = root.left if root.val > val else root.right return root # 返回找到的节点，如果没有找到则为None
上一篇：思科服务器的内存怎么查?
