前言
本篇为二叉树专题的刷题题单，总共6道题，每道题都有对应的链接。
边听歌边刷题吧~
654. 最大二叉树
链接： 最大二叉树
解题思路
- 每次以当前数组中最大的那个值为分割点
- 将数组分为左右子树构建左子树和右子树
AC代码
/** * 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) { if(nums.size()==0)return nullptr; int maxnum=0; for(int i=0;i<nums.size();++i) { if(nums[i]>nums[maxnum])maxnum=i; } int rootVal=nums[maxnum]; TreeNode* root=new TreeNode(rootVal); if(nums.size()==1)return root; vector<int> nleftTree(nums.begin(),nums.begin()+maxnum); vector<int> nrightTree(nums.begin()+maxnum+1,nums.end()); root->left=constructMaximumBinaryTree(nleftTree); root->right=constructMaximumBinaryTree(nrightTree); return root; } };
617. 合并二叉树
链接：617. 合并二叉树
解题思路
- 由题可得，两颗树都有的节点就相加
- 一个树没有就将另一棵树的那一节直接加到新的树的节点上
AC代码
/** * 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==nullptr)return root2; if(root2==nullptr)return root1; TreeNode* root = new TreeNode(0); root->val = root1->val + root2->val; root->left = mergeTrees(root1->left,root2->left); root->right = mergeTrees(root1->right,root2->right); return root; } };
700. 二叉搜索树中的搜索
解题思路
- 题目要求返回BST 中找到节点值等于 val 的节点的子树
- 其实就是找到那个节点
- 已知这颗树是二叉搜索树，那么就可以利用左边比根节点大，右边比根节点小的性质
- 其次还要使用一个变量来记录搜索的返回值
- 终止条件是节点为NULL时，说明到了叶子节点还没有找到
- 或者是节点的值相等说明找到了
AC代码
/** * 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=nullptr; if(root->val > val)result = searchBST(root->left,val); if(root->val < val)result = searchBST(root->right,val); return result; } };
98. 验证二叉搜索树
链接：98. 验证二叉搜索树
解题思路
- 记得二叉树的中序遍历是递增的不含重复元素的即可
AC代码
递归法
/** * 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* pre=nullptr; bool isValidBST(TreeNode* root) { if(root==nullptr)return true;//如果二叉搜索树为空，它也是二叉搜索树 bool l=isValidBST(root->left); //中序遍历时，二叉搜索树是顺序递增的(不包含重复元素) if(pre!=nullptr&&pre->val >= root->val)return false; pre=root;//记录前一个节点的值 bool r=isValidBST(root->right); return l&&r; } };
迭代法
class Solution { public: bool isValidBST(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; TreeNode* pre = NULL; // 记录前一个节点 while (cur != NULL || !st.empty()) { if (cur != NULL) { st.push(cur); cur = cur->left; // 左 } else { cur = st.top(); // 中 st.pop(); if (pre != NULL && cur->val <= pre->val) return false; pre = cur; //保存前一个访问的结点 cur = cur->right; // 右 } } return true; } };
530. 二叉搜索树的最小绝对差
解题思路
- 求最小差值、绝对值
- 已知二叉搜索树的中序遍历是递增且不含重复元素的
- 故可使用中序遍历，用一个变量记录前一个节点，如果前一个节点不为空则对比最小值
- 也可以将这个二叉搜索树的中序遍历为一个数组，然后遍历数组。
- 还可以使用栈来将树按照中序遍历的顺序读取然后比较
AC代码
递归法
class Solution { public: TreeNode*pre = nullptr; int res=INT_MAX; void getMinGap(TreeNode* root){ if(root==nullptr)return; getMinGap(root->left); if(pre!=nullptr){ res=min(res,root->val-pre->val); } pre=root; getMinGap(root->right); } int getMinimumDifference(TreeNode* root) { getMinGap(root); return res; } };
数组法
class Solution { private: vector<int> vec; void traversal(TreeNode* root) { if (root == NULL) return; traversal(root->left); vec.push_back(root->val); // 将二叉搜索树转换为有序数组 traversal(root->right); } public: int getMinimumDifference(TreeNode* root) { vec.clear(); traversal(root); if (vec.size() < 2) return 0; int result = INT_MAX; for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值 result = min(result, vec[i] - vec[i-1]); } return result; } };
迭代法
class Solution { public: int getMinimumDifference(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; TreeNode* pre = NULL; int result = INT_MAX; while (cur != NULL || !st.empty()) { if (cur != NULL) { // 指针来访问节点，访问到最底层 st.push(cur); // 将访问的节点放进栈 cur = cur->left; // 左 } else { cur = st.top(); st.pop(); if (pre != NULL) { // 中 result = min(result, cur->val - pre->val); } pre = cur; cur = cur->right; // 右 } } return result; } };
501. 二叉搜索树中的众数
解题思路
- 根据二叉搜索树的性质可以使用中序遍历
- 使用计数器记录相同的数字
- 一个记录前一个节点的变量，需要判断和前一个是否相同
- 如果节点不同就需要判断数量大小
- 数量相同就存入数组
- 数量更多就把数组清空将新的节点的数字存入数组，然后重新计数
- 如果碰到节点数字和前一个不同就将计数重置，更新pre
AC代码
/** * 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* pre=nullptr; vector<int> v; int maxcount=0; int count=0; void travel(TreeNode* root){ if(root==nullptr)return; travel(root->left); if(pre->val == root->val)count++; else if(pre->val != root->val){ pre = root; count=1; } if(count==maxcount){ v.push_back(root->val); } if(count>maxcount) { maxcount=count; v.clear(); v.push_back(root->val); } travel(root->right); return; } vector<int> findMode(TreeNode* root) { pre = root; travel(root); return v; } };
