二叉树的几道题

最大二叉树。先要找到数组中最大的值和对应的下标 最大的值构造根节点下标用来下一步分割数组。最大值所在的下标左区间 构造左子树 递归左子树最大值所在的下标右区间 构造右子树 递归右子树/** * 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(vectorint nums) { TreeNode*nodenew TreeNode(0); if(nums.size()1){ node-valnums[0]; return node; } int maxnum0; int maxindex0; for(int i0;inums.size();i){ if(nums[i]maxnum){ maxnumnums[i]; maxindexi; } } node-valmaxnum;//这里要判断最大值的位置,不是开头结尾。 if(maxindex0){ vectorintleftree(nums.begin(),nums.begin()maxindex); node-leftconstructMaximumBinaryTree(leftree); } if(maxindexnums.size()-1){ vectorintrightree(nums.begin()maxindex1,nums.end()); node-rightconstructMaximumBinaryTree(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()01到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到begin2即[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(root1NULL)return root2;//当它返回 t2 时它不再关心 t2 下面有什么直接整个挂过去。这在逻辑上阻止了对该分支的进一步递归。这就是为什么深度是有限的。 if(root2NULL)return root1; // 前序遍历 root1-val root2-val;//根 root1-leftmergeTrees(root1-left,root2-left);//左 root1-rightmergeTrees(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(rootNULL)return root; else if(root-valval)return root; else if(root-left!NULLroot-valval)return searchBST(root-left,val); else if(root-right!NULLroot-valval)return searchBST(root-right,val); return NULL; } };98.验证二叉搜索树中序遍历输出成了一个数组。class Solution { private: vectorintvec; public: void isValid(TreeNode* cur){ if(curNULL)return; isValid(cur-left); vec.push_back(cur-val); isValid(cur-right);//中序遍历可以用纸画一画 } bool isValidBST(TreeNode* root) { isValid(root); int sizevec.size(); for(int i1;isize;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(curNULL)return; getmin(cur-left); // 左 if(pre!NULL){ resultmin(result,abs(cur-val-pre-val));//后减去前 } precur; getmin(cur-right); } int getMinimumDifference(TreeNode* root) { getmin(root); return result; } };“不知道该看谁”是递归入门前最大的障碍。递归怎么看DeepSeek108. 将有序数组转换为二叉搜索树class Solution { public: TreeNode* sort(vectorint nums,int left,int right){//这里要用逗号不能用分号 if(leftright)return nullptr; int mid(leftright)/2; TreeNode*rootnew TreeNode(nums[mid]); root-leftsort(nums,left,mid-1); root-rightsort(nums,mid1,right); return root; } TreeNode* sortedArrayToBST(vectorint nums) { return sort(nums,0,nums.size()-1); } };if(leftright)return nullptr;这一行有什么用DeepSeek501.二叉搜索树中的众数力扣题目链接如果是搜索树怎么做如果不是搜索树怎么做如果不是搜索树遍历一遍用map统计最大值然后输出。class Solution { public: // 1. 定义哈希表统计每个数字出现的次数 unordered_mapint, int freq; // 2. 前序遍历中序后序都行把每个节点的值统计进哈希表 void dfs(TreeNode* root) { if (root nullptr) return; freq[root-val]; // 统计当前节点 dfs(root-left); dfs(root-right); } vectorint findMode(TreeNode* root) { vectorint 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; } };如果是搜索树这种题都一个套路和前面的二叉搜索树的最小绝对差一样左和右只需要递归写一个函数就行。在中间点的处理上再写真正的处理流程。