LeetCode 669.修剪二叉树
题目链接:
LeetCode 669.修剪二叉树
解题思路:
根据搜索二叉树性质,判断当前节点大小,进行迭代。注意当前节点不满足边界时,其左右子树可能仍然满足,
代码:
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(root==nullptr) return root;
if(root->val<low) return trimBST(root->right,low,high);
if(root->val>high) return trimBST(root->left,low,high);
root->left = trimBST(root->left,low,high);
root->right = trimBST(root->right,low,high);
return root;
}
};
LeetCode 108.将有序数组转换为二叉搜索树
题目链接:
LeetCode 108.将有序数组转换为二叉搜索树
解题思路:
先找到中间节点,作为根节点,之后将左右子树分别传进去,之后将索引作为变量进行改变参数。
代码:
class Solution {
public:
TreeNode* traversal(vector<int>&nums,int left,int right){
if(left>right) return nullptr;
int mid = (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(vector<int>& nums) {
return traversal(nums,0,nums.size()-1);
}
};
LeetCode 538.把二叉搜索树转换为累加数
题目链接:
LeetCode 538.把二叉搜索树转换为累加数
解题思路:
右中左遍历法,用pre来记录上一个节点的值。
代码:
class Solution {
public:
int pre = 0;
void traversal(TreeNode* root){
if(root==nullptr){
return;
}
traversal(root->right);
root->val +=pre;
pre = root->val;
traversal(root->left);
}
TreeNode* convertBST(TreeNode* root) {
traversal(root);
return root;
}
};