代码编织梦想

025.删除二叉搜索树中的节点_云泊683的博客-爱代码爱编程

题目链接: 450.删除二叉搜索树中的节点 大概思路: 题目要求: 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变,返回更新的二叉搜索树 思路: 按二叉搜索树的特性,遍历搜索到key值,因为要符合搜索树特性,所以要根据情况进行删除操作。返回删除后的节点。 递归三部

028.把二叉搜索树转换为累加树_云泊683的博客-爱代码爱编程

题目链接: 538. 把二叉搜索树转换为累加树 大概思路: 题目要求: 给一颗二叉搜索树,把里面各个节点的值,都等于树里面,所有大于等于这个节点的,各个节点值之和。如下图,比如 7只有8大于它,累加后,7变成 7+8=15.   思路: 二叉搜索树的中序遍历左中右,其遍历的节点值,可以看成是一个升序数组,那么右中左就是降序数组,从最大

026.修剪二叉搜索树_云泊683的博客-爱代码爱编程

题目链接: 669. 修剪二叉搜索树 大概思路: 题目要求: 给一颗二叉搜索树和一个区间 [low,hight ],要求修剪二叉搜索树,把里面超过区间边界的值都去除掉,然后返回它。 思路: 递归遍历遇见不在区间的节点值,先判断再修剪。因为搜索树规律,小于区间,去右子树修剪,大于区间去左子树修剪,修剪完返回左或右子树给节点值的上层(这里有父节

025. 二叉搜索树中的插入操作_云泊683的博客-爱代码爱编程

题目链接: 701. 二叉搜索树中的插入操作 大概思路: 题目要求: 给二叉搜索树和一个值,把值符合搜索树规则的插入到二叉搜索树中去。 思路: 自己思路:按给定的插入值,在搜索树里搜索他,因为插入值实际在搜索树里并不存在,所以遇见空值后(终止条件),添加插入值在空值节点上。 学后自己理解的思路:差不多 递归三部曲: 1.确定递归函数参

24. 二叉搜索树的最近公共祖先_云泊683的博客-爱代码爱编程

题目链接: 235. 二叉搜索树的最近公共祖先 大概思路: 题目要求: 给定一颗二叉搜索树,两个确定值q,p,要求q,p的最近公共祖先。 思路:     利用搜索树的特性,当q,p的值均小于遍历的节点值的时候,可以判断q,p均在根节点的左子树上,小于则在右子树上。这样下去,直到节点值在q和p之间,也就是一个q在左子树,一个p在右子树的时候,

023.二叉树的最近公共祖先_云泊683的博客-爱代码爱编程

题目链接: 236. 二叉树的最近公共祖先 大概思路: 题目要求: 给定一个二叉树, 找到该树中两个指定节点q,p的最近公共祖先x。(q、p一定存在且值不同) 最近公共祖先: 两个节点共同的祖先,同时深度尽可能大(其中一个可以是祖先本身) 思路: q,p的最近公共祖先有两种情况 第一种: 思路就是从底向上遍历,遇见q、p返回其值

020.验证二叉搜索树_云泊683的博客-爱代码爱编程

题目链接: 98. 验证二叉搜索树 大概思路: 题目要求: 判断给的二叉树是不是二叉搜索树。 二叉搜索树的特征: 节点的左子树所有节点的值均小于该节点的值,右节点反之,同时对搜索树的每一个节点都适用此规则。 中序遍历,遍历过程中节点的值是递增的。 数组法: 思路: 利用中序遍历在搜索树的特性,在遍历过程中,创建一个按中序遍历过的节点

018.合并二叉树_云泊683的博客-爱代码爱编程

题目链接: 617. 合并二叉树 大概思路: 题目要求: 给两个二叉树,要求返回一个合并的二叉树,相同节点位置的其数值相加,一个树的位置为空值而另一个树的位置有值的,则这颗树的有值节点填上空缺。 思路: 递归遍历的途中不断把两棵树相同位置的值相加,返回到树t1上,然后继续遍历,遇见空值把有值的一方返回,两个都没有就返回空 (返回上一层,大概理

019. 二叉搜索树中的搜索_云泊683的博客-爱代码爱编程

题目链接: 700. 二叉搜索树中的搜索 大概思路: 二叉搜索树的特性: 如果子树不为空,则左子树所有节点的值均小于其根节点的值,而右子树均大于。 01.递归法(递归三部曲流程) 1.确定递归函数参数和返回类型: 参数传入一个搜索树的节点,以及要搜索的值。 TreeNode* searchBST(TreeNode* root, in

016.从中序与后序遍历序列构造二叉树_云泊683的博客-爱代码爱编程

题目链接: 106. 从中序与后序遍历序列构造二叉树 大概思路: 题目要求: 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 思路: 先获取后序遍历的中,然后这个中再来分割中序数组的左和右,然后把分割的左和右带到

017.最大二叉树_云泊683的博客-爱代码爱编程

题目链接: 654. 最大二叉树 大概思路: 思路:(数组长度大于等于1) 传入一个互不相等的整数数组,然后用里面最大的值作根节点,同时以数组里最大的值作分割点,分为左右子树,然后左子树的最大值,作左子树的根节点,同时在上面划分的左子树的区域数组里,继续分割左右子树,同理再右,按照上面的做法不断递归,直到完成,返回这棵二叉树。   递归

015.路径总和 && 路径总和ii_云泊683的博客-爱代码爱编程

题目链接: 112. 路径总和 113. 路径总和 II 路径总和: 题目要求: 判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。 思路: 把targetSum 一开始就输入进来,然后遍历的过程中,不断减去经过节点的值,如果到叶子

014. 找树左下角的值_云泊683的博客-爱代码爱编程

题目链接:力扣 大概思路: 题目要求: 找到树的最底层里,最左边的节点的值。 递归法思路: 顺便一个遍历顺序,然后查找树最底层里,最左边的节点的值,然后返回。 树的最底层怎么判断? 到叶子节点就记录一个深度的最大值,同时记录这个叶子节点的值,然后继续遍历,遇见更大的深度,就改变收集的深度值和节点值,这样到遍历结束的时候,收集到的就是最

013.左叶子之和_云泊683的博客-爱代码爱编程

题目链接:力扣 大概思路: 左叶子的定义: 一个作父节点的左子树,是叶子节点。 思路: 后序遍历的基础上,加上判断左子树的逻辑,判断为左子树,返回值,然后左右子树的值相加。  递归三部曲: 1.确定递归函数的参数和返回值: 参数传入一个根节点,返回类型是int int sumOfLeftLeaves(TreeNode* root)

012.二叉树的所有路径_云泊683的博客-爱代码爱编程

题目链接:力扣 大概思路: 思路: 按题目要求,返回所有从根节点到叶子节点的路径。 遍历节点,path存储遍历过程中节点的值,遇见叶子节点返回。 在返回之前,把path的值,加入到结果集(需要把path里的值做下字符串转化),同时把path里的值弹出去,给下一条路径的记录留下空间。 遍历结束,返回结果集。 递归三部曲: 1.明确递归函数

011.平衡二叉树_云泊683的博客-爱代码爱编程

题目链接:力扣 大概思路: 平衡二叉树的定义: 二叉树的每一个节点,以其为根节点的时候,左右子树的高度差,不超过1,为平衡二叉树。 递归三部曲: 1.明确递归函数的参数和返回值: 参数为节点,返回值为int类型(为啥不直接返回布尔型?按卡老师的代码走) int getHeight(TreeNode* node){} 2.确定终止条件:

009.二叉树的最小深度_云泊683的博客-爱代码爱编程

题目链接:力扣 代码: class Solution { public: int getDepth(TreeNode* node) { if (node == NULL) return 0; int leftDepth = getDepth(node->left); // 左

007.二叉树的最大深度_云泊683的博客-爱代码爱编程

题目链接: 力扣 代码: 递归 class solution { public: int getdepth(treenode* node) { if (node == NULL) return 0; int leftdepth = getdepth(node->left); // 左

006.对称二叉树_云泊683的博客-爱代码爱编程

题目链接:力扣 代码: class Solution { public: bool compare(TreeNode* left, TreeNode* right) { // 首先排除空节点的情况 if (left == NULL && right != NULL) return false;

004.二叉树层序遍历_云泊683的博客-爱代码爱编程

题目链接:力扣 代码: class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> que; if (root != NULL) que.push(ro