当前位置：首页 > news >正文

代碼隨想录 day22|day23

news 来源：原创 2024/9/28 23:16:32

二叉树(完)

二叉搜索树的最近公共祖先
题意：找到二叉树的两个节点的祖先节点。
思路：二叉树的中序遍历特性：如果当前遍历的节点的值> 两个指定的节点的值。那么祖先节点就在当前节点左子树。如果当前遍历节点的值< 两个节点的值则祖先节点在节点右边。如果都不是那么当前节点是祖先节点。
核心代码

  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root->val >p->val && root->val > q->val){return   lowestCommonAncestor(root->left, p, q) ;// 利用搜索二叉树的性质：如果节点在左右节点之间，就是公共祖先。}else if(root->val < p->val && root->val < q->val){return lowestCommonAncestor(root->right, p, q);}return root ; }

二叉搜索树中的插入操作

题意：是把一个值插入到二叉搜索树中；
思路：最简单的办法是将值插入到叶子结点的左边或者右边。所以递归边界是节点的左右子树都是空，还有节点有左子树的但是右子树为空的情况。还有节点左子树为空，右子树不为空的情况。
思路2：不改变二叉树的结构直接在叶子节点接住生成的节点。通过当前root->val > val 就向左遍历。

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == NULL) {TreeNode* node = new TreeNode(val);return node;}if (root->val > val) root->left = insertIntoBST(root->left, val);if (root->val < val) root->right = insertIntoBST(root->right, val);return root;}
};

删除二叉搜索树中的节点

题意：在找到相应值之后如果左或者右孩子有一个不空直接删除；然后将其子返回即可。
但是在删除左右孩子都不为空的情况下，就需要将节点的左孩子直接赋给，右子树的最左叶子节点。然后返回右子树的根节点。这是根据二叉搜索树的性质来的。
核心代码

 TreeNode* deleteNode(TreeNode* root, int key) {if( root && root->val == key  ){if ( root->left != nullptr && root->right != nullptr) {// 因为左子树的节点都小于根节点的值，右子树的节点都大于根节点的值 // 将右子树的最左叶子节点，的左节点 的左边接上要删除的节点的右子树根节点。 TreeNode* tmp = root->right ;while(tmp->left){tmp = tmp->left ;} tmp->left =  root->left ;return root->right ; }else if(root->left == nullptr && root ->right != nullptr){TreeNode* tmp = root ; // delete tmp ; return root->right ; }else if(root->left != nullptr && root->right == nullptr){TreeNode* tmp = root ; // delete tmp ; return root->left ; }else{return nullptr ; }}if(root && root->val > key) root->left = deleteNode(root->left,key) ;if(root && root->val < key){root->right = deleteNode(root->right , key) ; }return root ; }

修剪二叉搜索树
虽然说着挺难，但是其实就是把删除二叉树的结点应用而已。
如果找到了不在范围的节点删除而已。
至于删除要分有左子节点没有右子节点的，有右子节点没有左子节点的。和左右子节点都没有的。另外需要从下往上回溯删除。不然就上一层的递归就接不着
核心代码

TreeNode* trimBST(TreeNode* root, int low, int high){if(root == nullptr){return nullptr ; }if(root && root->left ){root->left = trimBST(root->left , low ,high) ; }if(root && root->right ){root->right = trimBST(root->right , low ,high) ; }if(root->val <  low||root->val >  high) // 从下往上回溯，因为是从下往上处理的。 {cout<<"YEs"<<endl ; if(root->left == nullptr && root->right != nullptr){return root->right ; }else if(root->left != nullptr && root ->right == nullptr){return root->left ; }else if(root->left != nullptr && root->right != nullptr){TreeNode * cur = root->right ; while(cur->left != nullptr){cur = cur->left ; }cur->left = root->left ; return root->right ; }else {return nullptr ; }}return root ; }

将有序数组转换为二叉搜索树
想到二叉树的性质，根节点是中间节点。之后把序列分为左子树和右子树跟先前的序列与二叉搜索树的题有点像。
核心代码

/*** 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* sortedArrayToBST(vector<int>& nums){if(nums.size() == 0){return nullptr ; }vector<int> le  , re;int mid = nums.size() /2 ; int t = nums[ mid] ; for(int i = 0 ; i<mid ; ++i ){le.push_back(nums[i]) ; }for(int i = mid+1 ; i <nums.size() ; ++i){re.push_back(nums[i]) ; }TreeNode * root = new TreeNode(t) ; root->left = sortedArrayToBST(le) ; root->right = sortedArrayToBST(re) ; return root ; }
};

把二叉搜索树转换为累加树
题意：使用双指针的算法。不过要改变遍历顺序改为右中左。之后root-.>val += prev->val ;
核心代码

   void trival(TreeNode * root){if(root == nullptr){return  ; }convertBST(root->right) ;if(pre != nullptr){root->val += pre->val ; }pre  = root ; convertBST(root->left) ; }