669. 修剪二叉搜索树
难。没来得及弄。周六做
108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
**高度平衡 **二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
#答案自己敲的。不够简洁。有空看一下答案
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
int size = nums.size();
if (size == 0) {
return nullptr;
}
int mid = size/2;
TreeNode* root = new TreeNode(nums[mid]);
TreeNode* left = nullptr;
TreeNode* right = nullptr;
if (mid > 0) {
vector<int> leftNums(nums.begin(), nums.begin() + mid);
left = sortedArrayToBST(leftNums);
}
if (mid < size) {
vector<int> rightNums(nums.begin() + mid + 1, nums.end());
right = sortedArrayToBST(rightNums);
}
root->left = left;
root->right = right;
return root;
}
};
538. 把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
关键点是读懂题目,先右后左
递归
public:
void travelSal(TreeNode* root) {
if (root != nullptr) {
travelSal(root->right);
root->val += pre;
pre = root->val;
travelSal(root->left);
}
}
TreeNode* convertBST(TreeNode* root) {
travelSal(root);
return root;
}
};
迭代
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
int pre = 0;
stack<TreeNode*> st;
TreeNode* cur = root;
while(!st.empty() || cur != nullptr) {
if (cur != nullptr) {
st.push(cur);
cur = cur->right;
} else {
cur = st.top();
st.pop();
cur->val += pre;
pre = cur->val;
cur = cur->left;
}
}
return root;
}
};