做网站哪些技术,徐州网站开发培训,游戏代理0加盟费,公司注册地址怎么变更654.最大二叉树
注意类似用数组构造二叉树的题目#xff0c;每次分隔尽量不要定义新的数组#xff0c;而是通过下标索引直接在原数组上操作#xff0c;这样可以节约时间和空间上的开销。
题目链接/文章讲解#xff1a;代码随想录
lass Solution {
private:// 在左闭右开…654.最大二叉树
注意类似用数组构造二叉树的题目每次分隔尽量不要定义新的数组而是通过下标索引直接在原数组上操作这样可以节约时间和空间上的开销。
题目链接/文章讲解代码随想录
lass Solution {
private:// 在左闭右开区间[left, right)构造二叉树TreeNode* traversal(vectorint nums, int left, int right) {if (left right) return nullptr;// 分割点下标maxValueIndexint maxValueIndex left;for (int i left 1; i right; i) {if (nums[i] nums[maxValueIndex]) maxValueIndex i;}TreeNode* root new TreeNode(nums[maxValueIndex]);// 左闭右开[left, maxValueIndex)root-left traversal(nums, left, maxValueIndex);// 左闭右开[maxValueIndex 1, right)root-right traversal(nums, maxValueIndex 1, right);return root;}
public:TreeNode* constructMaximumBinaryTree(vectorint nums) {return traversal(nums, 0, nums.size());}
};617.合并二叉树
优先掌握递归。
代码随想录
递归法
class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 NULL) return t2;if (t2 NULL) return t1;// 重新定义新的节点不修改原有两个树的结构TreeNode* root new TreeNode(0);root-val t1-val t2-val;root-left mergeTrees(t1-left, t2-left);root-right mergeTrees(t1-right, t2-right);return root;}
};迭代法
class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 NULL) return t2;if (t2 NULL) return t1;queueTreeNode* que;que.push(t1);que.push(t2);while(!que.empty()) {TreeNode* node1 que.front(); que.pop();TreeNode* node2 que.front(); que.pop();// 此时两个节点一定不为空val相加node1-val node2-val;// 如果两棵树左节点都不为空加入队列if (node1-left ! NULL node2-left ! NULL) {que.push(node1-left);que.push(node2-left);}// 如果两棵树右节点都不为空加入队列if (node1-right ! NULL node2-right ! NULL) {que.push(node1-right);que.push(node2-right);}// 当t1的左节点 为空 t2左节点不为空就赋值过去if (node1-left NULL node2-left ! NULL) {node1-left node2-left;}// 当t1的右节点 为空 t2右节点不为空就赋值过去if (node1-right NULL node2-right ! NULL) {node1-right node2-right;}}return t1;}
};700.二叉搜索树中的搜索
递归和迭代都掌握
二叉搜索树的特点是根节点比左孩子节点要大比右孩子节点要小。
代码随想录
递归法:注意遍历左右子树的时候要返回函数如果左右子树都遍历不到的时候就返回空
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root NULL || root-val val) return root;if (root-val val) return searchBST(root-left, val);if (root-val val) return searchBST(root-right, val);return NULL;}
};class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root ! NULL) {if (root-val val) root root-left;else if (root-val val) root root-right;else return root;}return NULL;}
};98.验证二叉搜索树
遇到 搜索树一定想着中序遍历这样才能利用上特性。
注意根节点要比所有左子树的所有节点都要小要比所有右子树的节点都要大。
方法一maxValue来记录前一个节点的数值如果前一个节点的数值按照中序的遍历顺序数组的值应该是递增的如果是平衡二叉树的话否则就不是平衡二叉树 方法二用pre记录前一个节点当前节点和pre进行比较pre进行更新。
class Solution {
public:TreeNode* pre NULL; // 用来记录前一个节点bool isValidBST(TreeNode* root) {if (root NULL) return true;bool left isValidBST(root-left);if (pre ! NULL pre-val root-val) return false;pre root; // 记录前一个节点bool right isValidBST(root-right);return left right;}
};也可以用迭代法只用增加一个指针指向前一个节点和判断什么时候返回fasle以及更新前一个指针的。 注意while中是两个条件是或的情况
代码随想录
class Solution {
public:bool isValidBST(TreeNode* root) {stackTreeNode* 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;}
};
