网站ui设计收费,做礼品建什么网站,一起做网店白沟,wordpress怎么查找文件669. 修剪二叉搜索树 题目链接#xff1a;669. 修剪二叉搜索树 文档讲解#xff1a;代码随想录 状态#xff1a;还可以 思路#xff1a; 如果节点的值在[low, high]之间#xff0c;则递归修剪它的左子树和右子树。 节点值小于low#xff1a;如果节点的值小于low#xff…669. 修剪二叉搜索树 题目链接669. 修剪二叉搜索树 文档讲解代码随想录 状态还可以 思路 如果节点的值在[low, high]之间则递归修剪它的左子树和右子树。 节点值小于low如果节点的值小于low则修剪后的树不会包含这个节点及其左子树直接返回修剪后的右子树。 节点值大于high如果节点的值大于high则修剪后的树不会包含这个节点及其右子树直接返回修剪后的左子树。
题解
public TreeNode trimBST(TreeNode root, int low, int high) {// 如果当前节点为空返回nullif (root null) {return null;}// 如果当前节点的值在[low, high]之间if (root.val high root.val low) {// 修剪左子树并将其连接到当前节点的左子树root.left trimBST(root.left, low, high);// 修剪右子树并将其连接到当前节点的右子树root.right trimBST(root.right, low, high);} else if (root.val low) {// 如果当前节点的值小于low则修剪后的树不包括当前节点及其左子树直接返回右子树return trimBST(root.right, low, high);} else {// 如果当前节点的值大于high则修剪后的树不包括当前节点及其右子树直接返回左子树return trimBST(root.left, low, high);}// 返回当前节点return root;
}
108.将有序数组转换为二叉搜索树 题目链接108. 将有序数组转换为二叉搜索树 文档讲解代码随想录 状态还行 思路找到数组的中间元素将其作为当前子树的根节点。递归地对数组的左半部分构建左子树。递归地对数组的右半部分构建右子树。
public TreeNode sortedArrayToBST(int[] nums) {// 调用辅助函数getBST来构建BSTreturn getBST(nums, 0, nums.length - 1);
}public TreeNode getBST(int[] nums, int start, int end) {// 基本情况如果start大于end返回nullif (start end) {return null;}// 计算中间索引int mid start (end - start) / 2;// 创建根节点TreeNode node new TreeNode(nums[mid]);// 递归构建左子树node.left getBST(nums, start, mid - 1);// 递归构建右子树node.right getBST(nums, mid 1, end);// 返回根节点return node;
}
538.把二叉搜索树转换为累加树 题目链接538. 把二叉搜索树转换为累加树 文档讲解代码随想录 状态还行 思路通过观察可以发现是一个右-中-左遍历的顺序因此可以从大到小遍历节点并累加节点值。
题解
int sum 0;public TreeNode convertBST(TreeNode root) {if (root null) {return null;}// 递归处理右子树TreeNode node new TreeNode();node.right convertBST(root.right);// 更新累加和并更新当前节点的值sum root.val;node.val sum;// 递归处理左子树node.left convertBST(root.left);return node;
}
