赞
踩
题目列表
代码随想录地址:https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
给你二叉搜索树的根节点 root
,同时给定最小边界low
和最大边界 high
。通过修剪二叉搜索树,使得所有节点的值在[low, high]
中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。
示例 1:
输入:root = [1,0,2], low = 1, high = 2
输出:[1,null,2]
示例 2:
输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出:[3,2,null,1]
提示:
写的递归代码,因为迭代代码不存在特别清晰的思路,因此没写。
/* * @lc app=leetcode.cn id=669 lang=cpp * * [669] 修剪二叉搜索树 */ // @lc code=start /** * 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* trimBST(TreeNode* root, int low, int high) { if(root == nullptr) return nullptr; 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; } }; // @lc code=end
代码随想录地址:
https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E9%80%92%E5%BD%92
给你一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1:
输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
示例 2:
输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示:
nums
按 严格递增 顺序排列就是将中间节点作为头节点开始构建二叉树。
/* * @lc app=leetcode.cn id=108 lang=cpp * * [108] 将有序数组转换为二叉搜索树 */ // @lc code=start /** * 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 { private: //变量left和right表示构建二叉树的元素在数组中的范围 //使用的是[left, right]前闭后闭区间 TreeNode* traverse(vector<int>& nums, int left, int right) { if(left > right) return nullptr; int mid = left + ((right - left)/2);//这样写是为了防止溢出int //构造根节点 TreeNode* node = new TreeNode(nums[mid]); //构造根节点的左孩子 node->left = traverse(nums, left, mid - 1); //构造根节点的右孩子 node->right = traverse(nums, mid + 1, right); //返回根节点 return node; } public: TreeNode* sortedArrayToBST(vector<int>& nums) { return traverse(nums, 0, nums.size() - 1); } }; // @lc code=end
稍微有点复杂,需要复习
/* * @lc app=leetcode.cn id=108 lang=cpp * * [108] 将有序数组转换为二叉搜索树 */ // @lc code=start /** * 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) { //迭代写法,就是实现递归的步骤 //为什么使用队列而不用栈,因为本题的思路先进先出还是先进后出不影响结果 //nodeQue每次入队的是元素0 if(nums.size() == 0) return nullptr; //这个队列存储现场 queue<TreeNode*> nodeQue; queue<int> leftQue; queue<int> rightQue; TreeNode* root = new TreeNode(0); //类似于保存现场 nodeQue.push(root);//将根节点入栈 leftQue.push(0); rightQue.push(nums.size() - 1); while(!nodeQue.empty()) { //处理节点 TreeNode* node = nodeQue.front(); nodeQue.pop(); int left = leftQue.front(); leftQue.pop(); int right = rightQue.front(); rightQue.pop(); int mid = left + (right - left)/2; //其实就是这里需要知道地址 //这个地址就按顺序存在队列中 node->val = nums[mid]; //处理左边的节点 if(left <= mid - 1) { node->left = new TreeNode(0); nodeQue.push(node->left); leftQue.push(left); rightQue.push(mid - 1); } //处理右边的节点 if(right >= mid + 1) { node->right = new TreeNode(0); nodeQue.push(node->right); leftQue.push(mid + 1); rightQue.push(right); } } return root; } }; // @lc code=end
代码随想录地址:https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node
的新值等于原树中大于或等于 node.val
的值之和。
提醒一下,二叉搜索树满足下列约束条件:
**注意:**本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1:
输入:[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]
示例 2:
输入:root = [0,null,1]
输出:[1,null,1]
示例 3:
输入:root = [1,0,2]
输出:[3,3,2]
示例 4:
输入:root = [3,2,4,1]
输出:[7,9,4,10]
提示:
0
和
1
0
4
10^4
104 之间。就是右中左的遍历顺序。
/* * @lc app=leetcode.cn id=538 lang=cpp * * [538] 把二叉搜索树转换为累加树 */ // @lc code=start /** * 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 { private: int pre; void traverse(TreeNode* node) { if(node == nullptr) return; traverse(node->right);//右 //中 node->val += pre; pre = node->val; //左 traverse(node->left); return; } public: TreeNode* convertBST(TreeNode* root) { pre = 0; traverse(root); return root; } }; // @lc code=end
/* * @lc app=leetcode.cn id=538 lang=cpp * * [538] 把二叉搜索树转换为累加树 */ // @lc code=start /** * 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* convertBST(TreeNode* root) { if(root == nullptr) return root; stack<TreeNode*> st; int pre = 0; st.push(root); while(!st.empty()) { TreeNode* node = st.top(); st.pop(); if(node == nullptr) { node = st.top(); st.pop(); node->val += pre; pre = node->val; } else { if(node->left) st.push(node->left); st.push(node); st.push(nullptr); if(node->right) st.push(node->right); } } return root; } }; // @lc code=end
代码随想录地址:
https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。