游戏开发公司排名,wordpress宝塔优化,做网站深紫色搭配什么颜色,互联网营销师是干什么系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于左程云算法课程进行的#xff0c;每个知识点的修正和深入主要参考… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于左程云算法课程进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 二叉树理论基础基本知识 待补充140 https://www.bilibili.com/video/BV16i4y1d7PL/?p9vd_sourcece626ff62ed6a7b65ff163189a520fb1二叉树的递归套路例题二叉树深度优先遍历*二叉树广度优先遍历*二叉树最大深度二叉树最小深度求树中结点的数量判断是否为平衡二叉树 相关题目翻转二叉树二叉树是否对称二叉树的所有路径左叶子之和求二叉树最左下的叶子符合总和的路径 构建二叉树树的序列化105. 从前序与中序遍历序列构造二叉树106. 从中序与后序遍历序列构造二叉树654. 构建二叉树*二叉树的双指针遍历654. 最大二叉树 二叉搜索树查找二叉搜索树的指定值98. 验证二叉搜索树530. 二叉搜索树的最小绝对差 236. 二叉树的最近公共祖先 235. 二叉搜索树的最近公共祖先 450. 删除二叉搜索树中的节点 669. 修剪二叉搜索树 108. 将有序数组转换为二叉搜索树669. 修剪二叉搜索树 [LeetCode] 333. 最大 BST 子树 参考博客 点此到文末惊喜↩︎ 二叉树理论基础
基本知识
二叉树数据结构struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};二叉树递归套路 建立Info结构体数据元素为向左右子树索要的信息的集合递归出口考虑递归到底部应该如何返回info信息划分状态一般为选择和不选择两种情况进行考虑并修改info信息返回info信息返回的实际是整合后的一颗树的info信息
待补充140 https://www.bilibili.com/video/BV16i4y1d7PL/?p9vd_sourcece626ff62ed6a7b65ff163189a520fb1
二叉树的递归套路例题
题目链接【二叉树的直径】
struct Info {int max_distance;int height;Info(int dis, int h) : max_distance(dis), height(h){}
};
Info Process(Node *root) {// 递归出口叶子结点时高度和最大距离都为0if (root nullptr) return new Info(0, 0);// 获取左右子树的信息Info left_info Process(root-left);Info right_info Process(root-right);// 根据左右子树信息构建本树的信息int height max(left_info.height, right_info.height) 1;int max_distance max(max(left_info.max_distance, right_info.max_distance), left_info.height right_info.height 1)// 返回本树info信息return new Info(max_distance, height);}
二叉树深度优先遍历*
Leetcode题目链接递归序 原理递归出口、递归左子树、递归右子树三个部分中间及后面的范围成为其递归处理范围。过程每个结点都会被经历三次第一次是根结点处理范围、左子树处理范围和右子树处理范围本质递归出口和子递归函数每一部分都是递归该递归处理范围 // 递归序
void f(TreeNode *root) {if (root nullptr) return ;// 根结点处理范围f(root-left); // 左子树处理范围f(root-right); // 右子树处理范围
}递归式 前序遍历任何子树的处理顺序都是先根节点、再左子树然后右子树中序遍历任何子树的处理顺序都是先左子树、再根节点然后右子树后序遍历任何子树的处理顺序都是先左子树、再右子树然后根节点 // 前序遍历
void Traversal(TreeNode *root) {if (root nullptr) return ;Doing(root-val); // 中Traversal(root-left); // 左Traversal(root-right); // 右
}
// 中序遍历
void Traversal(TreeNode *root) {if (root nullptr) return ;Traversal(root-left); // 左Doing(root-val); // 中Traversal(root-right); // 右
}
// 后序遍历
void Traversal(TreeNode *root, vectorint vec) {if (root nullptr) return ;Traversal(root-left); // 左Traversal(root-right); // 右vec.emplace_back(root-val);// 中
}递归和非递归 任何递归函数都可以通过自己设计压栈的方式改成非递归 非递归将前序、中序和后序统一化处理将遍历核心顺序进行逆序转化 初始化声明结果容器、栈、根非空则入栈算法栈非空每次取栈顶元素。判断结点是否为空若为空则弹出并逆序压入对应元素若非空则弹出结点和空结点并进行处理 vectorint Traversal(TreeNode* root) {// 初始化vectorint result; // 结果容器stackTreeNode* st; // 深度的栈if (root ! NULL) // 根非空则入栈st.push(root);// 遍历源容器while (!st.empty()) {TreeNode* node st.top(); // if (node ! NULL) {st.pop();// 算法变化的部分遍历的逆序// 中st.push(node); st.push(NULL);// 右if (node-right) st.push(node-right); // 左if (node-left) st.push(node-left); } else {// 对值节点的处理st.pop();// 弹出空值结点node st.top();st.pop();// 结点处理result.push_back(node-val);}}return result;
}二叉树广度优先遍历*
Leetcode题目链接递归法// 递归参数如果需要修改要进行引用传递
void traversal(TreeNode* cur, vectorvectorint result, int depth) {// 递归出口if (cur nullptr) return;// 递归体if (result.size() depth) // 扩容result.push_back(vectorint());// 原地构建数组result[depth].push_back(cur-val);// 顺序压入对应深度的数组中order(cur-left, result, depth 1);order(cur-right, result, depth 1);
}
vectorvectorint levelOrder(TreeNode* root) {// 初始化一般为递归形参vectorvectorint result;int depth 0;// 递归调用traversal(root, result, depth);// 返回结果return result;
}非递归法vectorvectorint levelOrder(TreeNode* root) {// 初始化vectorvectorint result; // 结果容器queueTreeNode* que; // 广度的队列if(root ! nullptr) // 根非空则入列 que.push(root);// 算法while (!que.empty()) { // 队列非空vectorint vec; // 结果存放TreeNode* node; // 过程记录int size que.size(); // 初始化记录每层要遍历的根节点数量for (int i 0; i size; i) { // que.size()会变化// 处理结点node que.front(); // 先记录后弹出避免复杂逻辑que.pop(); if (node-left) que.push(node-left);if (node-right) que.push(node-right);// 对每个结点的处理vec.push_back(node-val);}// 对每层的处理result.push_back(vec);}// 输出return result;
}二叉树最大深度
递归法// 递归只考虑当前层不要过于考虑整体
int depth(TreeNode* root) {// 1. 如果当前 root 为 null说明当前层的深度就是 0 if (!root) {return 0;}// 2. 分别计算左子树和右子树的深度int L depth(root-left);int R depth(root-right);// 3. 获取当前树的左子树和右子树深度的较大值加 1 本层深度return max(L,R) 1;
}
// 简略版
int depth(TreeNode* cur) { //计算最大深度return (cur nullptr) ? 0 : max(depth(cur-left), depth(cur-right)) 1;
}非递归法int MaxDepth(TreeNode *root) {int depth 0; // 结果queueTreeNode* que; // 队列if (root ! nullptr) // 根入列que.push(root);while (!que.empty()) {TreeNode *node;// 层次遍历int size que.size();for (int i 0; i size; i) {node que.front();que.pop();if (node-left) que.push(node-left);if (node-right) que.push(node-right);}// 层数1depth;} return depth;
}二叉树最小深度
递归法 二叉树的五种形态 空二叉树只有根节点只有左子树只有右子树左右子树都有 int minDepth(TreeNode* root) {// 空二叉树if (root NULL) return 0;// 只有左子树if (root-left ! NULL root-right NULL) {return 1 minDepth(root-left);}// 只有右子树if (root-left NULL root-right ! NULL) {return 1 minDepth(root-right);}// 左右子树都非空return 1 min(minDepth(root-left), minDepth(root-right));
}非递归法 找到第一个左右孩子均为空的即为最小深度 int minDepth(TreeNode* root) {if (root NULL) return 0;int depth 0;queueTreeNode* que;que.push(root);while(!que.empty()) {int size que.size();depth; // 记录最小深度for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (!node-left !node-right) { // 第一个左右孩子均空为最小深度return depth;if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}}return depth;
}求树中结点的数量
递归法 递归法要只考虑单层的逻辑 int getNodesNum(TreeNode* cur) {if (cur NULL) return 0;int leftNum getNodesNum(cur-left); // 左int rightNum getNodesNum(cur-right); // 右int treeNum leftNum rightNum 1; // 中return treeNum;
}非递归法int CountNodes(TreeNode *root) {int count 0; // 结果queueTreeNode* que; // 队列if (root ! nullptr) // 根入队que.push(root);// 队列非空则执行while (!que.empty()) {TreeNode * node; int size que.size(); // 该层宽度for (int i 0; i size; i) { // 层次遍历count;// 结点的处理node que.front();que.pop();if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return count;
}判断是否为平衡二叉树
递归法 后序遍历和求树的高度的模板改进
// 初始化ans为true最后看ans是否为false即可
int depth(TreeNode* root, bool ans) {if(!root) return 0;// 后序遍历int left1depth(root-left, ans);int right1depth(root-right, ans);if(abs(left-right)1)ansfalse;// 对根结点的处理// 递归出口return max(left,right); // 返回树的高度
}
// 尾递归优化效率高
bool isBalanced(TreeNode* root) {if (root nulllptr) return true;return abs(depth(root-left) - depth(root-right)) 1 isBalanced(root-left) isBalanced(root-right);
}相关题目
翻转二叉树
翻转二叉树 对于二叉树的操作都是从二叉树的遍历衍生出来的 // 前序遍历
void Traversal(TreeNode *cur){if(cur nullptr)return ;swap(cur-left, cur-right); // 树的本质是地址的值if(cur-left) Traversal(cur-left);if(cur-right) Traversal(cur-right);
}
// 调用函数
TreeNode* invertTree(TreeNode* root) {if(root nullptr) return nullptr;Traversal(root);return root;
}二叉树是否对称
101. 对称二叉树 对称二叉树要比较的不是左右节点而是比较根节点的左右子树是否值相等 bool compare(TreeNode* left, TreeNode* right) {if (left NULL right ! NULL) return false;else if (left ! NULL right NULL) return false;else if (left NULL right NULL) return true;else if (left-val ! right-val) return false; // 左右都不空才能访问值else return compare(left-left, right-right) compare(left-right, right-left);
}
bool isSymmetric(TreeNode* root) {if (root NULL) return true;return compare(root-left, root-right);
} 有点东西的写法这是哪个题的判断链表的入口的ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *A headA, *B headB;// 核心在于交换头节点while (A ! B) {A A ! nullptr ? A-next : headB;B B ! nullptr ? B-next : headA;}return A;
}二叉树的所有路径
递归 数字转化成字符串to_string(number)字符串后追加子串str.append(subStr)字符串删除某个位置之后的字符str.erase(position) // 数字型
void dfs(TreeNode*root,vectorintpath, vectorvectorint res)
{if(!root) return; //根节点为空直接返回// 中path.push_back(root-val); //作出选择if(!root-left !root-right) //如果到叶节点 {res.push_back(path);return;}// 左dfs(root-left,path,res); //继续递归// 右dfs(root-right,path,res);
}
// 字符型
void binaryTree(TreeNode* root,string path,vectorstringres)
{if(rootNULL) return ;path.append(to_string(root-val));path.append(-);if(root-leftNULLroot-rightNULL{path.erase(path.length()-2);res.push_back(path);}binaryTree(root-left,path,res);binaryTree(root-right,path,res);
}
vectorstring binaryTreePaths(TreeNode* root) {string path;vectorstringres;binaryTree(root,path,res);return res;
}左叶子之和
求二叉树的左叶子之和 遍历所有节点对所求的特殊节点进行约束求值 void postorder(TreeNode *root, int result){if(root nullptr) return ;if(root-left) postorder(root-left, result);if(root-right) postorder(root-right, result);// 中if(root-left ! nullptr root-left-left nullptr root-left-right nullptr)result root-left-val;
}迭代法int sumOfLeftLeaves(TreeNode* root) {// 初始化stackTreeNode* st;if(root ! nullptr) st.push(root);int res 0;// 迭代while(!st.empty()){TreeNode* cur st.top();if(cur ! nullptr){st.pop();st.push(cur);st.push(nullptr);if(cur-right) st.push(cur-right);if(cur-left) st.push(cur-left);}else{st.pop();cur st.top();st.pop();if(cur-left ! nullptr cur-left-left nullptr cur-left-right nullptr)res cur-left-val;} }// 结果处理return res;
}求二叉树最左下的叶子
513. 找树左下角的值 层次遍历最后一层的第一个就是最左下的叶子 int findBottomLeftValue(TreeNode* root) {queueTreeNode * q;if(root ! nullptr)q.push(root);int res 0;while(!q.empty()){int size q.size();for(int i 0; i size; i){TreeNode * cur q.front();q.pop();// 每层的第一个即最左的节点if(i 0) res cur-val;if(cur-left) q.push(cur-left);if(cur-right) q.push(cur-right);}}return res;
}符合总和的路径
112. 路径总和 增加结点就加值不符合就回溯进行减值。 bool hasPathSum(TreeNode* root, int targetSum) {// 初始化stackTreeNode* st;if(root ! nullptr) st.push(root);int sum 0;// 迭代while(!st.empty()){TreeNode *cur st.top();if(cur ! nullptr){st.pop();st.push(cur);st.push(nullptr);sum cur-val;if(cur-right) st.push(cur-right);if(cur-left) st.push(cur-left);}else{st.pop();cur st.top();st.pop();// 节点判断if(sum targetSum cur-left nullptr cur-right nullptr){return true;}else{// 回溯sum - cur-val;}}}return false;
}构建二叉树
树的序列化
树的序列化和反序列化 序列化树的遍历在输出时将所有结点的左右孩子补全没有的使用null代替反序列化按照什么遍历方式序列化就按照什么遍历方式反序列化 深度优先的的序列化和反序列化
// 序列化
void Serialize(Node *head, queuestring que) {if (head nullptr) {que.push(-1); // 空标记} else {que.push(to_string(head-val));Serialize(head-left, que);Serialize(head-right, que);}
}
// 反序列化
Node *Build(queuestring que) {int val atoi(que.front());que.pop();if (val -1) return nullptr;Node *root new Node(val);root-left Build(que);root-right Build(que);return root; // 建立完成返回
}105. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 TreeNode* traversal(vectorint preorder, vectorint inorder) {// 递归出口if (preorder.empty() true) return nullptr;// 建立根结点TreeNode *root new TreeNode(preorder[0], nullptr, nullptr);// 查找当前结点在中序序列中的位置vectorint::iterator itr find(inorder.begin(), inorder.end(), preorder[0]);// 划分中序序列vectorint inorder_left(inorder.begin(), itr); // key左闭右开vectorint inorder_right(itr 1, inorder.end());// 划分前序序列:根据左右子树的数量vectorint preorder_left( preorder.begin()1, preorder.begin()1(itr - inorder.begin()));vectorint preorder_right( preorder.begin()1(itr - inorder.begin()), preorder.end());//创建左右子树, 并将它们的根节点赋值给当前节点的指针root-left buildTree(preorder_left, inorder_left);root-right buildTree(preorder_right, inorder_right);return root;
}106. 从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树 通过始末位置指示容器范围避免每次调用的vector创建开销 // 中序区间[inorderBegin, inorderEnd)后序区间[postorderBegin, postorderEnd)
TreeNode* traversal (vectorint inorder, int inorderBegin, int inorderEnd, vectorint postorder, int postorderBegin, int postorderEnd){// 每次都是先从后序找所以后序没有即完成if (postorderBegin postorderEnd) return NULL;// 分界点为后序最后一个int rootValue postorder[postorderEnd - 1];TreeNode* root new TreeNode(rootValue);if (postorderEnd - postorderBegin 1) return root;// 查找前序序列中的分界下标int delimiterIndex;for (delimiterIndex inorderBegin; delimiterIndex inorderEnd; delimiterIndex) {if (inorder[delimiterIndex] rootValue) break;}// 切割中序数组// 左中序区间左闭右开[leftInorderBegin, leftInorderEnd)int leftInorderBegin inorderBegin;int leftInorderEnd delimiterIndex;// 右中序区间左闭右开[rightInorderBegin, rightInorderEnd)int rightInorderBegin delimiterIndex 1;int rightInorderEnd inorderEnd;// 切割后序数组// 左后序区间左闭右开[leftPostorderBegin, leftPostorderEnd)int leftPostorderBegin postorderBegin;int leftPostorderEnd postorderBegin delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size// 右后序区间左闭右开[rightPostorderBegin, rightPostorderEnd)int rightPostorderBegin postorderBegin (delimiterIndex - inorderBegin);int rightPostorderEnd postorderEnd - 1; // 排除最后一个元素已经作为节点了// root-left traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);root-right traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);return root;
}TreeNode* buildTree(vectorint inorder, vectorint postorder) {if (inorder.size() 0 || postorder.size() 0) return NULL;// 左闭右开的原则return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}654. 构建二叉树*
654. 最大二叉树 通过始末位置指示容器范围避免每次调用的vector创建开销 // 在左闭右开区间[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;
}二叉树的双指针遍历
530. 二叉搜索树的最小绝对差 注意INT_MAX的溢出问题
int getMinimumDifference(TreeNode* root) {// 基本初始化stackTreeNode* st;if (root ! nullptr) st.push(root);int result INT_MAX;TreeNode* prior new TreeNode(-100000); // 给根节点前面一个初始化条件// 迭代while (!st.empty()) {TreeNode* cur st.top();if (cur ! NULL) {// 弹出根节点再重排序st.pop();if (cur-right) st.push(cur-right);st.push(cur);st.push(NULL);if (cur-left) st.push(cur-left);}else {st.pop();// 出nullcur st.top();st.pop();// 节点处理result min(result, cur-val - prior-val);prior cur;// 迭代条件要放在最后}}return result;
}654. 最大二叉树
617. 合并二叉树 如果两颗树有个相同位置的节点一个为空另一个不是。则应该直接链接过去因为这样可以保证后面的也过去 // 递归
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;
}
// 非递归方式
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;
}二叉搜索树
查找二叉搜索树的指定值
利用二叉搜索树的左小右大 栈、队列和树中元素的访问要注意判空防止访问溢出 bool handleNode(TreeNode* root, int key) {// 健壮性检查if (root nullptr) return false;// 双指针TreeNode *cur root;TreeNode *prev root;while(cur ! nullptr){// 结点的处理if (cur-val key) {Doing();}// 指针移动prev cur;if (key cur-val) {if (cur-left)cur cur-left;else return root;} else {if (cur-right)cur cur-right;else return root;}}return root;
}98. 验证二叉搜索树
98. 验证二叉搜索树 中序遍历下输出的二叉搜索树节点的数值是有序序列 // **********中序遍历形成一个递增数组**************
vectorint vec;
void inorder(TreeNode *root){if(root nullptr) return ;inorder(root-left);vec.push_back(root-val);inorder(root-right);
}
// 判断是否中序遍历的数组是递增的
bool isValidBST(TreeNode* root){inorder(root);for(int i 0; i vec.size()-1; i){if(vec[i] vec[i1])// 二叉搜索树的中序排列是严格递增的return false;}return true;
}// *********************纯递归**********************
bool isValid(TreeNode* current,long left,long right){// 单层逻辑if(currentnullptr) return true;else if(current-valleft||current-valright) return false;// 递归return isValid(current-left,left,current-val)isValid(current-right,current-val,right);
}
bool isValidBST(TreeNode* root) {return isValid(root,LONG_MIN,LONG_MAX);
}530. 二叉搜索树的最小绝对差
530. 二叉搜索树的最小绝对差 思路中序遍历下输出的二叉搜索树节点的数值是有序序列。顺序判断相邻值的绝对值保存最小的即可双指针在树内应用双指针本质是对于一个序列的遍历。 int getMinimumDifference(TreeNode* root) {// 初始化条件stackTreeNode* st;if(root ! nullptr) st.push(root);int res INT_MAX;TreeNode *prior new TreeNode(-1000000);while(!st.empty()){TreeNode* cur st.top();if(cur ! nullptr){st.pop();// 中序遍历if(cur-right) st.push(cur-right);st.push(cur);st.push(nullptr);if(cur-left) st.push(cur-left);}else{st.pop();cur st.top();st.pop();// 节点处理res min(res, cur-val - prior-val);prior cur;// 迭代条件}}return res;
}236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先 后序遍历是一个天然的自低向上的回溯过程状态的向上传递通过判断左右子树是否出现了p和q如果出现p或q则通过回溯值上传到父节点 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root NULL)return NULL;// 每次对返回的结点进行if(root p || root q) return root;TreeNode* left lowestCommonAncestor(root-left, p, q);TreeNode* right lowestCommonAncestor(root-right, p, q);// 结点的处理是尽量返回结点if(left NULL)return right;if(right NULL)return left; if(left right) // p和q在两侧return root;return NULL; // 必须有返回值}235. 二叉搜索树的最近公共祖先
235. 二叉搜索树的最近公共祖先 思路自上而下搜索遇到的第一个节点值在p和q之间的值即为最近公共祖先 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while(root) {if (root-val p-val root-val q-val) {root root-left;} else if (root-val p-val root-val q-val) {root root-right;} else return root;}return NULL;
}450. 删除二叉搜索树中的节点
450. 删除二叉搜索树中的节点 思路框架 TreeNode* deleteNode(TreeNode* root, int key) {// 健壮性检查if(root nullptr) return nullptr;// 基本初始化TreeNode *cur root;TreeNode *prior root;while (cur ! nullptr){// 符合条件值的处理if(cur-val key){if(cur-left nullptr || cur-right nullptr){// 两个都空if(cur-left nullptr cur-right nullptr) return nullptr;// 被删除节点只有一个孩子或均为空if(key prior-val){// cur是左子树prior-left cur-right;return root; }else{prior-right n cur-right;return root; }}else{// 被删除节点有两个孩子TreeNode *curLeft cur-left;cur cur-right;while(cur-left ! nullptr){cur cur-left;}cur-left curLeft;if(key prior-val){// cur是左子树prior-left prior-left-right;return root; }else{prior-right prior-right-right;return root; }}}prior cur;// 前迭代// 左右节点处理if(key cur-val){if(cur-left){cur cur-left;}else{// 找不到return root;}}else{if(cur-right){cur cur-right;}else{// 找不到return root;}}}return root;}669. 修剪二叉搜索树
669. 修剪二叉搜索树// 1. 确定递归函数的返回类型及参数返回类型是递归算法的输出值类型参数是递归算法的输入
TreeNode* trimBST(TreeNode* root, int low, int high) {// 2. 递归终止条件if (root nullptr ) return nullptr;// 3.节点处理return保留的状态if (root-val low) {// 保留更大的右半部分TreeNode* right trimBST(root-right, low, high);return right;}if (root-val high) {// 保留更小的左半部分TreeNode* left trimBST(root-left, low, high); return left;}// 4.迭代条件root-left trimBST(root-left, low, high); // root-left接入符合条件的左孩子root-right trimBST(root-right, low, high); // root-right接入符合条件的右孩子return root;
}108. 将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树TreeNode* traversal(vectorint nums, int left, int right) {// 递归出口if (left right) return nullptr;// 运算int mid left ((right - left) / 2);// 防止求和溢出TreeNode* root new TreeNode(nums[mid]);// 递归迭代root-left traversal(nums, left, mid - 1);root-right traversal(nums, mid 1, right);return root;
}
// 主调函数
TreeNode* sortedArrayToBST(vectorint nums) {TreeNode* root traversal(nums, 0, nums.size() - 1);return root;
}669. 修剪二叉搜索树
669. 修剪二叉搜索树// 1. 确定递归函数的返回类型及参数返回类型是递归算法的输出值类型参数是递归算法的输入
TreeNode* trimBST(TreeNode* root, int low, int high) {// 2. 递归终止条件if (root nullptr ) return nullptr;// 3.节点处理return保留的状态if (root-val low) {// 保留更大的右半部分TreeNode* right trimBST(root-right, low, high);return right;}if (root-val high) {// 保留更小的左半部分TreeNode* left trimBST(root-left, low, high); return left;}// 4.迭代条件root-left trimBST(root-left, low, high); // root-left接入符合条件的左孩子root-right trimBST(root-right, low, high); // root-right接入符合条件的右孩子return root;
}[LeetCode] 333. 最大 BST 子树
代码// 1. 确定递归函数的返回类型及参数返回类型是递归算法的输出值类型参数是递归算法的输入
TreeNode* trimBST(TreeNode* root, int low, int high) {// 2. 递归终止条件if (root nullptr ) return nullptr;// 3.节点处理return保留的状态if (root-val low) {// 保留更大的右半部分TreeNode* right trimBST(root-right, low, high);return right;}if (root-val high) {// 保留更小的左半部分TreeNode* left trimBST(root-left, low, high); return left;}// 4.迭代条件root-left trimBST(root-left, low, high); // root-left接入符合条件的左孩子root-right trimBST(root-right, low, high); // root-right接入符合条件的右孩子return root;
}少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 代码随想录 letcode
