专业旅游网站制作,ui设计分析案例,网站建设推广语,口腔医院网站做优化算法题
Leetcode 654.最大二叉树
题目链接:654.最大二叉树
大佬视频讲解#xff1a;最大二叉树视频讲解 个人思路 大概思路就是在数组中 找最大值的节点作为当前节点#xff0c;用最大值的index切割左右子树的区间#xff0c;往复循环到数组元素为0#xff1b; 解法 递…算法题
Leetcode 654.最大二叉树
题目链接:654.最大二叉树
大佬视频讲解最大二叉树视频讲解 个人思路 大概思路就是在数组中 找最大值的节点作为当前节点用最大值的index切割左右子树的区间往复循环到数组元素为0 解法 递归法
按照思路来看递归法是不错的选择可以采用前序遍历因为是先构造中间节点然后递归构造左子树和右子树。 1.确定递归函数的参数和返回值参数 传入的是存放元素的数组返回该数组构造的二叉树的头结点返回类型是指向节点的指针。 2.确定终止条件 题目中说了输入的数组大小一定是大于等于1的所以不用考虑小于1的情况那么当递归遍历的时候如果传入的数组大小为1说明遍历到了叶子节点了。 那么应该定义一个新的节点并把这个数组的数值赋给新的节点然后返回这个节点。 这表示一个数组大小是1的时候构造了一个新的节点并返回。 3.确定单层递归的逻辑 1.先要找到数组中最大的值和对应的下标 最大的值构造根节点下标用来下一步分割数组 2.最大值所在的下标左区间 构造左子树 这里要判断maxValueIndex 0因为要保证左区间至少有一个数值。 3.最大值所在的下标右区间 构造右子树 判断maxValueIndex (nums.size() - 1)确保右区间至少有一个数值。 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;}
} 时间复杂度:O(n)遍历整棵树每个元素最多被访问一次 空间复杂度:O(n);递归树的高度h Leetcode 617.合并二叉树
题目链接:617.合并二叉树
大佬视频讲解:合并二叉树视频讲解 个人思路 这个和构造一颗二叉树差不多只是需要同时操控两棵树所以只用同时遍历两棵二叉树把树A和树B的节点值相加到树A最后返回树A即可 解法
递归法 class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 null) return root2;//2.确定终止条件if (root2 null) return root1;//3.确定单层递归的逻辑root1.val root2.val;//两颗数节点值相加root1.left mergeTrees(root1.left,root2.left);//左树合并root1.right mergeTrees(root1.right,root2.right);//右树合并return root1;//1.确定递归函数的参数和返回类型}
} 时间复杂度:O(n)最差遍历一遍树 空间复杂度:O(n);递归树的高度h 迭代法
也可以用队列模拟的层序遍历同时遍历将值加到一棵树上最后返回这棵树
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 null) return root2;if (root2 null) return root1;QueueTreeNode queue new LinkedList();queue.offer(root1);queue.offer(root2);while (!queue.isEmpty()) {TreeNode node1 queue.poll();TreeNode node2 queue.poll();// 此时两个节点一定不为空val相加node1.val node1.val node2.val;// 如果两棵树左节点都不为空加入队列if (node1.left ! null node2.left ! null) {queue.offer(node1.left);queue.offer(node2.left);}// 如果两棵树右节点都不为空加入队列if (node1.right ! null node2.right ! null) {queue.offer(node1.right);queue.offer(node2.right);}// 若node1的左节点为空直接赋值if (node1.left null node2.left ! null) {node1.left node2.left;}// 若node1的右节点为空直接赋值if (node1.right null node2.right ! null) {node1.right node2.right;}}return root1;}
} 时间复杂度:O(n)遍历2棵树 空间复杂度:O(n);使用两个队列 Leetcode 700.二叉搜索树中的搜索
题目链接:700.二叉搜索树中的搜索 大佬视频讲解:二叉搜索树中的搜索视频讲解
个人思路
对于普通二叉树和搜素树都能递归法一层层找找到节点值与目标值相同时返回该节点。 解法 回顾一下二叉搜索树它是一个有序树 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树 递归法
可以根据二叉搜索树的特性(leftroot, rightroot)优化一下递归 class Solution {public TreeNode searchBST(TreeNode root, int val) {if (root null || root.val val) {//终止条件return root;//返回参数}//递归逻辑if (val root.val) {return searchBST(root.left, val);//往左搜索} else {return searchBST(root.right, val);//往右搜索}}
}
递归搜索普通二叉树的代码如下
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);}
} 时间复杂度:O(n)最差遍历一遍树 空间复杂度:O(n);递归树的高度h 迭代法
因为二叉搜索树的特殊性也就是节点的有序性可以不使用辅助栈或者队列就可以写出迭代法。
对于一般二叉树递归过程中还有回溯的过程例如走一个左方向的分支走到头了那么要调头在走右分支。而对于二叉搜索树不需要回溯的过程因为节点的有序性就帮我们确定了搜索的方向。
例如要搜索元素为11的节点不需要搜索其他节点也不需要做回溯查找的路径已经规划好了。中间节点如果大于11就向左走如果小于11就向右走如图 class Solution {public TreeNode searchBST(TreeNode root, int val) {//不用栈也能模拟递归while (root ! null)if (val root.val) root root.left;else if (val root.val) root root.right;else return root;return null;}
} 时间复杂度:O(n)遍历整棵树 空间复杂度:O(1);没有使用其他辅助空间 迭代搜索普通二叉树代码如下
class Solution {// 迭代普通二叉树public TreeNode searchBST(TreeNode root, int val) {if (root null || root.val val) {return root;}StackTreeNode stack new Stack();stack.push(root);while (!stack.isEmpty()) {TreeNode pop stack.pop();if (pop.val val) {return pop;}if (pop.right ! null) {stack.push(pop.right);}if (pop.left ! null) {stack.push(pop.left);}}return null;}
} 时间复杂度:O(n)遍历整棵树 空间复杂度:O(n);使用栈模拟递归 Leetcode 98.验证二叉搜索树
题目链接:98.验证二叉搜索树
大佬视频讲解:验证二叉搜索树视频讲解 个人思路
刚刚做完搜索树但如何验证搜索树的思路却不清晰...
解法 递归法
首先这道题目比较容易犯个错误 不能单纯的比较左节点小于中间节点右节点大于中间节点。 因为搜索树要比较的是 左子树所有节点小于中间节点右子树所有节点大于中间节点。 例如 [10,5,15,null,null,6,20] 这个case 节点10大于左节点5小于右节点15但右子树里出现了一个6 这就不符合了 然后继续递归三步走这里采用中序遍历因为要先知道根节点的值再去比较左右子节点 1.确定递归函数返回值以及参数 如果没有找到这个节点就遍历了整个树如果找到不符合的节点了立刻返回。 2.确定终止条件 如果是空节点 也是二叉搜索树 3.确定单层递归的逻辑 中序遍历一直更新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;}
} 时间复杂度:O(n)遍历二叉树 空间复杂度:O(n);递归树的高度h 迭代法
可以用栈模拟递归中序遍历
class Solution { public boolean isValidBST(TreeNode root) {if (root null) {return true;}StackTreeNode stack new Stack();TreeNode pre null;while (root ! null || !stack.isEmpty()) {while (root ! null) {stack.push(root);root root.left;// 左}// 中处理节点判断大小TreeNode pop stack.pop();if (pre ! null pop.val pre.val) {return false;}pre pop;root pop.right;// 右}return true;}
} 时间复杂度:O(n)遍历二叉树 空间复杂度:O(n);模拟递归的栈 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
