营销型网站模板,免费学编程国内网站,网站网站建设设计,建设网站需要租用服务器669.修剪二叉搜索树
题目链接#xff1a;669. 修剪二叉搜索树
思路#xff1a;确定递归函数定义#xff0c;根据定义去构造二叉搜索树。
class Solution {// 定义#xff1a;删除 BST 中小于 low 和大于 high 的所有节点#xff0c;返回结果 BSTpublic TreeNode trimBS…669.修剪二叉搜索树
题目链接669. 修剪二叉搜索树
思路确定递归函数定义根据定义去构造二叉搜索树。
class Solution {// 定义删除 BST 中小于 low 和大于 high 的所有节点返回结果 BSTpublic TreeNode trimBST(TreeNode root, int low, int high) {if (root null) return null;if (root.val low) {// 直接返回 root.right// 等于删除 root 以及 root 的左子树return trimBST(root.right, low, high);}if (root.val high) {// 直接返回 root.left// 等于删除 root 以及 root 的右子树return trimBST(root.left, low, high);}// 闭区间 [lo, hi] 内的节点什么都不做root.left trimBST(root.left, low, high);root.right trimBST(root.right, low, high);return root;}
}108.将有序数组转换为二叉搜索树
题目链接108. 将有序数组转换为二叉搜索树
思路题目要求构成一个左右平衡的二叉树先找到数组的中间节点作为根节点然后根据中间节点左边的数组构建左子树中间节点右边的数组构建右子树。递归过程中可以看出循环不变量的重要性
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return build(nums, 0, nums.length - 1);}// 左闭右闭区间[left, right]TreeNode build(int[] nums, int left, int right){if(left right){return null;}int mid left (right - left) / 2;TreeNode root new TreeNode(nums[mid]);root.left build(nums, left, mid - 1);root.right build(nums, mid 1, right);return root;}
}538.把二叉搜索树转换为累加树
题目链接538. 把二叉搜索树转换为累加树
思路维护一个外部累加变量 sum在遍历 BST 的过程中增加 sum同时把 sum 赋值给 BST 中的每一个节点就将 BST 转化成累加树了。但是注意顺序正常的中序遍历顺序是先左子树后右子树这里需要反过来先右子树后左子树。
class Solution {public TreeNode convertBST(TreeNode root) {traverse(root);return root;}// 记录累加和int sum 0;void traverse(TreeNode root) {if (root null) {return;}// 注意先右子树后左子树traverse(root.right);// 维护累加和sum root.val;// 将 BST 转化成累加树root.val sum;traverse(root.left);}
}二叉树总结
二叉树题目中的注意点
1、二叉树中大部分题目使用递归要想到递归三部曲
1、确定返回值参数。2、确定终止条件。3、确定单层逻辑。
2、二叉树的题目遍历顺序非常重要拿到一个题目首先要确定遍历顺序。
3、遇到二叉搜索树的题目不要忘记二叉搜索树中序遍历的特性。
二叉树题目类型
1、二叉树构造类题目无论普通二叉树还是二叉搜索树一定前序都是先构造中节点。
2、求解普通二叉树属性一般是后序一般要通过递归函数的返回值做计算。
3、求解二叉搜索树属性一定要优先考虑中序遍历的特性。 注意在普通二叉树的属性中一般为后序但是单纯求深度就用前序二叉树找所有路径也用了前序这是为了方便让父节点指向子节点。所以求普通二叉树的属性还是要具体问题具体分析。
