二叉树的几道题
最大二叉树。
- 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
- 最大值所在的下标左区间 构造左子树 递归左子树
- 最大值所在的下标右区间 构造右子树 递归右子树
/** * 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<int>& nums) { TreeNode*node=new TreeNode(0); if(nums.size()==1){ node->val=nums[0]; return node; } int maxnum=0; int maxindex=0; for(int i=0;i<nums.size();i++){ if(nums[i]>maxnum){ maxnum=nums[i]; maxindex=i; } } node->val=maxnum;//这里要判断最大值的位置,不是开头结尾。 if(maxindex>0){ vector<int>leftree(nums.begin(),nums.begin()+maxindex); node->left=constructMaximumBinaryTree(leftree); } if(maxindex<nums.size()-1){ vector<int>rightree(nums.begin()+maxindex+1,nums.end()); node->right=constructMaximumBinaryTree(rightree);} return node; } };如果最大值在开头结尾，会是什么情况？
代码里巧妙地用了两个if条件来保护切割操作，这就是它能“存活”下来的原因。这里一开始我没想到，导致代码报错。
情况 1：最大值在开头（maxindex == 0）
假设数组为nums = [5, 1, 3]（最大值 5 在索引 0）。
根节点：
node->val = 5。左子树判断：
if(maxindex > 0)→0 > 0为假。不会创建
leftree，也不会调用递归。结果：
node->left保持构造函数里的默认值nullptr（空）。这是正确的，因为根节点左边没有元素了。
右子树判断：
if(maxindex < nums.size()-1)→0 < 2为真。创建
rightree，范围是nums.begin()+0+1到end，即[1, 3]。递归去构建右子树。
最终树结构：
5没有左孩子，只有右子树。
情况 2：最大值在结尾（maxindex == nums.size() - 1）
假设数组为nums = [1, 3, 5]（最大值 5 在索引 2）。
根节点：
node->val = 5。左子树判断：
if(maxindex > 0)→2 > 0为真。创建
leftree，范围是begin到begin+2，即[1, 3]。递归去构建左子树。
右子树判断：
if(maxindex < nums.size()-1)→2 < 2为假。不会创建
rightree，也不会调用递归。结果：
node->right保持默认的nullptr。这是正确的，因为根节点右边没有元素了。
最终树结构：
5没有右孩子，只有左子树。
如果有负数怎么找最大值？
INT_MIN（极小值）
INT_MAX（极大值）
合并二叉树
这道题逻辑代码非常简单，但是巧妙地借助了第一棵树作为载体，而不是新建一棵树，
class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if(root1==NULL)return root2;//当它返回 t2 时，它不再关心 t2 下面有什么，直接整个挂过去。这在逻辑上阻止了对该分支的进一步递归。这就是为什么深度是有限的。 if(root2==NULL)return root1; // 前序遍历 root1->val += root2->val;//根 root1->left=mergeTrees(root1->left,root2->left);//左 root1->right=mergeTrees(root1->right,root2->right); return root1; } };700.二叉搜索树中的搜索
- 确定终止条件
如果root为空，或者找到这个数值了，就返回root节点。
if (root == NULL || root->val == val) return root;- 确定单层递归的逻辑
看看二叉搜索树的单层递归逻辑有何不同。
因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
代码如下：
TreeNode* result = NULL; if (root->val > val) result = searchBST(root->left, val); if (root->val < val) result = searchBST(root->right, val); return result;很多录友写递归函数的时候 习惯直接写searchBST(root->left, val)，却忘了 递归函数还有返回值。
递归函数的返回值是什么? 是 左子树如果搜索到了val，要将该节点返回。 如果不用一个变量将其接住，那么返回值不就没了。
所以要result = searchBST(root->left, val)。
总体代码如下：
class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { if(root==NULL)return root; else if(root->val==val)return root; else if(root->left!=NULL&&root->val>val)return searchBST(root->left,val); else if(root->right!=NULL&&root->val<val)return searchBST(root->right,val); return NULL; } };98.验证二叉搜索树
中序遍历输出成了一个数组。
class Solution { private: vector<int>vec; public: void isValid(TreeNode* cur){ if(cur==NULL)return; isValid(cur->left); vec.push_back(cur->val); isValid(cur->right);//中序遍历，可以用纸画一画 } bool isValidBST(TreeNode* root) { isValid(root); int size=vec.size(); for(int i=1;i<size;i++){ if(vec[i-1]>=vec[i])return false; } return true; } };530.二叉搜索树的最小绝对差
我最简单的思路：和上一道题一样随便怎么遍历，记录一个数组，sort一下，再相减不就行了
答：这样是对的！但是题解给了一个更简单的方法：因为这个搜索树大小排列时有序的，所以直接用中序遍历两两一前一后比就行。
class Solution { public: int result = INT_MAX; TreeNode* pre = NULL; void getmin(TreeNode*cur){ if(cur==NULL)return; getmin(cur->left); // 左 if(pre!=NULL){ result=min(result,abs(cur->val-pre->val));//后减去前 } pre=cur; getmin(cur->right); } int getMinimumDifference(TreeNode* root) { getmin(root); return result; } };“不知道该看谁”是递归入门前最大的障碍。递归怎么看：
DeepSeek
108. 将有序数组转换为二叉搜索树
class Solution { public: TreeNode* sort(vector<int>& nums,int left,int right){//这里要用逗号，不能用分号！！！！ if(left>right)return nullptr; int mid=(left+right)/2; TreeNode*root=new TreeNode(nums[mid]); root->left=sort(nums,left,mid-1); root->right=sort(nums,mid+1,right); return root; } TreeNode* sortedArrayToBST(vector<int>& nums) { return sort(nums,0,nums.size()-1); } };if(left>right)return nullptr;这一行有什么用？
DeepSeek
501.二叉搜索树中的众数
力扣题目链接
如果是搜索树怎么做，如果不是搜索树怎么做？
如果不是搜索树：
遍历一遍，用map统计最大值然后输出。
class Solution { public: // 1. 定义哈希表，统计每个数字出现的次数 unordered_map<int, int> freq; // 2. 前序遍历（中序后序都行），把每个节点的值统计进哈希表 void dfs(TreeNode* root) { if (root == nullptr) return; freq[root->val]++; // 统计当前节点 dfs(root->left); dfs(root->right); } vector<int> findMode(TreeNode* root) { vector<int> result; if (root == nullptr) return result; // 3. 遍历整棵树，填充 freq 哈希表 dfs(root); // 4. 找出众数出现的最大次数（频率） int maxCount = 0; for (auto& pair : freq) { if (pair.second > maxCount) { maxCount = pair.second; } } // 5. 找出所有出现次数 == maxCount 的数字，加入结果 for (auto& pair : freq) { if (pair.second == maxCount) { result.push_back(pair.first); } } return result; } };如果是搜索树：
这种题都一个套路，和前面的二叉搜索树的最小绝对差一样，左和右只需要递归写一个函数就行。在中间点的处理上再写真正的处理流程。