漳州企业网站建设,桓台建设局网站,网站上线 文案,购物app大全669. 修剪二叉搜索树 题目链接#xff1a;修剪二叉搜索树 题目描述#xff1a; 给你二叉搜索树的根节点 root #xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树#xff0c;使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对…669. 修剪二叉搜索树 题目链接修剪二叉搜索树 题目描述 给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。 解题思路 因为二叉搜索树的顺序性所以可以根据根节点先找出修剪好的根节点位置当根节点不在范围内时直接经过比较大小可以知道能够修剪掉一半二叉树也就是根节点在左子树或右子树。之后找到范围内的根节点之后再按照同样的规律修建左子树和右子树。
代码实现 递归法
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root null){return root;}if(root.vallow){return trimBST(root.right,low,high);}if(root.valhigh){return trimBST(root.left,low,high);}root.left trimBST(root.left,low,high);root.right trimBST(root.right,low,high);return root;}
}迭代法
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(rootnull){return root;}//先找到在范围内的根节点while(root!null(root.val low || root.val high)){if(root.vallow){rootroot.right;}else {root root.left;}}//剪支左子树TreeNode cur root;while(cur!null){while(cur.left!nullcur.left.vallow){cur.left cur.left.right;}cur cur.left;}//剪支右子树cur root;while(cur!null){while(cur.right!nullcur.right.valhigh){cur.right cur.right.left;}cur cur.right;}return root;}
}108. 将有序数组转换为二叉搜索树 题目链接将有序数组转换为二叉搜索树 题目描述 给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 解题思路 本题比较简单因为二叉搜索树的特性所以每次寻找中间节点作为根节点即可完成高度平衡的要求所以只要先找到根节点也就是中间节点在递归处理左区域的节点和右区域的节点即可。只要保证区间的开闭一致即可。
代码实现 递归法
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return traversal(nums, 0, nums.length - 1);}public TreeNode traversal(int[] nums, int begin, int end) {if (begin end) {return null;}TreeNode node new TreeNode(nums[(end begin) / 2]);node.left traversal(nums, begin, (end begin) / 2 - 1);node.right traversal(nums, (end begin) / 2 1, end);return node;}
}迭代法
class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length 0){return null;}TreeNode root new TreeNode();QueueTreeNode rootQue new LinkedList();QueueInteger leftQue new LinkedList();QueueInteger rightQue new LinkedList();rootQue.offer(root);leftQue.offer(0);rightQue.offer(nums.length-1);while(!rootQue.isEmpty()){TreeNode node rootQue.poll();int left leftQue.poll();int right rightQue.poll();int mid (rightleft)/2;//根节点赋值node.val nums[mid];//处理左区间if(leftmid){node.left new TreeNode();rootQue.offer(node.left);leftQue.offer(left);rightQue.offer(mid-1);}//处理右区域if(rightmid){node.right new TreeNode();rootQue.offer(node.right);leftQue.offer(mid1);rightQue.offer(right);}}return root;}
}538. 把二叉搜索树转换为累加树 题目链接把二叉搜索树转换为累加树 题目描述 给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下二叉搜索树满足下列约束条件 节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。 解题思路 本题比较简单因为二叉搜索树时左中右的大小只要从右下角更新节点值不断采用当前节点值等于当前节点值加前一个节点值即可也就是只要采用逆向中序遍历就可得出最终的结果。
代码实现 递归法
class Solution {int sum 0;public TreeNode convertBST(TreeNode root) {if(root null){return root;}convertBST(root.right);sum root.val;root.val sum;convertBST(root.left);return root;}
}迭代法
class Solution {public TreeNode convertBST(TreeNode root) {if (root null) {return root;}int pre 0;StackTreeNode sta new Stack();TreeNode cur root;while (cur ! null || !sta.isEmpty()) {if (cur ! null) {sta.push(cur);cur cur.right;} else {cur sta.pop();cur.val pre cur.val;pre cur.val;cur cur.left;}}return root;}
}
