新乡网站建设哪家公司好,阿里巴巴做国际网站多少钱,wordpress小工具popular categories,建站怎么赚钱文章目录 654.最大二叉树617.合并二叉树700.二叉搜索树中的搜索98.验证二叉搜索树 654.最大二叉树
题目链接 654.最大二叉树 题目描述 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下#xff1a; 二叉树的根是数组中的最大元素。左子树是通过数组中最… 文章目录 654.最大二叉树617.合并二叉树700.二叉搜索树中的搜索98.验证二叉搜索树 654.最大二叉树
题目链接 654.最大二叉树 题目描述 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下 二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构建最大二叉树并且输出这个树的根节点。 思路 构造树一般采用的是前序遍历因为先构造中间节点然后递归构造左子树和右子树。 先要找到数组中最大的值和对应的下标最大的值构造根节点下标用来下一步分割数组。最大值所在的下标左区间构造左子树。最大值所在的下标右区间构造右子树。 实现代码
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return constructMaximumBinaryTree1(nums, 0, nums.length);}public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {if (rightIndex - leftIndex 1) {// 没有元素了return null;}if (rightIndex - leftIndex 1) {// 只有一个元素return new TreeNode(nums[leftIndex]);}int maxIndex leftIndex;// 最大值所在位置int maxVal nums[maxIndex];// 最大值for (int i leftIndex 1; i rightIndex; i) {if (nums[i] maxVal){maxVal nums[i];maxIndex i;}}TreeNode root new TreeNode(maxVal);// 根据maxIndex划分左右子树root.left constructMaximumBinaryTree1(nums, leftIndex, maxIndex);root.right constructMaximumBinaryTree1(nums, maxIndex 1, rightIndex);return root;}
}617.合并二叉树
题目链接 617.合并二叉树 题目描述 给定两个二叉树想象当你将它们中的一个覆盖到另一个上时两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠那么将他们的值相加作为节点合并后的新值否则不为 NULL 的节点将直接作为新二叉树的节点。 思路 和遍历一个树逻辑是一样的只不过传入两个树的节点同时操作。 确定递归函数的参数和返回值 首先要合入两个二叉树那么参数至少是要传入两个二叉树的根节点返回值就是合并之后二叉树的根节点。确定终止条件 因为是传入了两个树那么就有两个树遍历的节点t1 和 t2如果t1 NULL 了两个树合并就应该是 t2 了如果t2也为NULL也无所谓合并之后就是NULL。 反过来如果t2 NULL那么两个数合并就是t1如果t1也为NULL也无所谓合并之后就是NULL。确定单层递归的逻辑 单层递归的逻辑就比较好写了这里我们重复利用一下t1这个树t1就是合并之后树的根节点就是修改了原来树的结构。 实现代码
class Solution {// 递归public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 null) return root2;if (root2 null) return root1;root1.val root2.val;root1.left mergeTrees(root1.left,root2.left);root1.right mergeTrees(root1.right,root2.right);return root1;}
}700.二叉搜索树中的搜索
题目链接 700.二叉搜索树中的搜索 题目描述 给定二叉搜索树BST的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在则返回 NULL。 思路 确定递归函数的参数和返回值 递归函数的参数传入的就是根节点和要搜索的数值返回的就是以这个搜索数值所在的节点。 确定终止条件 如果root为空或者找到这个数值了就返回root节点。 确定单层递归的逻辑 如果root-val val搜索左子树如果root-val val就搜索右子树最后如果都没有搜索到就返回NULL。 实现代码
class Solution {public TreeNode searchBST(TreeNode root, int val) {if (root null || root.val val) {return root;}TreeNode left searchBST(root.left, val);if (left ! null) {return left;}return searchBST(root.right, val);}
}98.验证二叉搜索树
题目链接 98.验证二叉搜索树 题目描述 给定一个二叉树判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征 节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 思路 确定递归函数返回值以及参数 要定义一个longlong的全局变量用来比较遍历的节点是否有序因为后台测试数据中有int最小值所以定义为longlong的类型初始化为longlong最小值。 确定终止条件 如果是空节点也是二叉搜索树。 确定单层递归的逻辑 中序遍历一直更新maxVal一旦发现maxVal root-val就返回false注意元素相同时候也要返回false。 实现代码
class Solution {// 递归TreeNode max;public boolean isValidBST(TreeNode root) {if (root null) {return true;}// 左boolean left isValidBST(root.left);if (!left) {return false;}// 中if (max ! null root.val max.val) {return false;}max root;// 右boolean right isValidBST(root.right);return right;}
}
