怎样做自己的摄影网站,百度联盟怎么做自己的网站,seo查询网站是什么,二手房网站制作教程654. 最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点#xff0c;其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums…654. 最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 最大二叉树 。
方法一递归
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return construct(nums, 0, nums.length - 1);}public TreeNode construct(int[] nums, int left, int right) {if (left right) {return null;}int best left;for (int i left 1; i right; i) {if (nums[i] nums[best]) {best i;}}TreeNode node new TreeNode(nums[best]);node.left construct(nums, left, best - 1);node.right construct(nums, best 1, right);return node;}
}这段代码定义了一个名为 Solution 的类其中有两个方法用于构建一棵最大二叉树。最大二叉树的定义是树中的每个节点都是对应输入数组中从该节点所在位置开始往后的子数组中的最大值。以下是代码的详细解释 public TreeNode constructMaximumBinaryTree(int[] nums) 是主要接口接收一个整型数组 nums并返回根据该数组构建的最大二叉树的根节点。它通过调用重载的 construct 方法来实现这个功能初始化传入整个数组的起始下标 0 和结束下标 nums.length - 1。 public TreeNode construct(int[] nums, int left, int right) 是一个递归方法用于根据输入数组 nums 从索引 left 到 right 的子数组构建最大二叉树。 首先检查边界条件如果 left right表示当前子数组为空没有节点可构建返回 null。然后在 left 到 right 的范围内找到最大值的索引 best。初始化时假设 best 为 left通过遍历该范围内的元素如果发现更大的值则更新 best。创建一个新的 TreeNode其值为 nums[best]即当前子数组中的最大值。递归调用 construct 方法构建左子树参数为 left 和 best - 1意在构建以当前最大值左侧子数组为基础的最大二叉树。同样递归调用构建右子树参数为 best 1 和 right构建以当前最大值右侧子数组为基础的最大二叉树。最后返回当前节点完成以 nums[best] 为根节点的子树构建。
通过这样的递归过程代码能够高效地遍历整个数组构建出整棵最大二叉树。这种方法充分利用了分治思想每次递归调用都确保了以当前区间的最大值为根节点从而保证了构建出的二叉树满足题目要求。
方法二单调栈
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {int n nums.length;DequeInteger stack new ArrayDequeInteger();int[] left new int[n];int[] right new int[n];Arrays.fill(left, -1);Arrays.fill(right, -1);TreeNode[] tree new TreeNode[n];for (int i 0; i n; i) {tree[i] new TreeNode(nums[i]);while (!stack.isEmpty() nums[i] nums[stack.peek()]) {right[stack.pop()] i;}if (!stack.isEmpty()) {left[i] stack.peek();}stack.push(i);}TreeNode root null;for (int i 0; i n; i) {if (left[i] -1 right[i] -1) {root tree[i];} else if (right[i] -1 || (left[i] ! -1 nums[left[i]] nums[right[i]])) {tree[left[i]].right tree[i];} else {tree[right[i]].left tree[i];}}return root;}
}这段代码实现了一个名为 Solution 的类其中的 constructMaximumBinaryTree 方法接收一个整型数组 nums并根据这个数组构建一棵最大二叉树。最大二叉树的特性是每个节点都是其子树包括该节点中最大值的节点。与之前递归的解法不同这段代码采用了单调栈和两次遍历的方法来构造这棵树。
代码逻辑步骤如下 初始化变量和数据结构 n 为数组 nums 的长度。stack 是一个单调递减的整数栈用于存放数组下标保证栈顶元素对应的 nums 值是栈中已处理元素中的最大值。left 和 right 数组分别记录每个元素在最大二叉树中的左孩子和右孩子的索引初始化为 -1。tree 数组用于存储根据 nums 创建的 TreeNode 对象。 第一次遍历 遍历 nums 数组创建每个节点并压入栈中。同时根据栈的状态更新每个节点的左右孩子索引在 left 和 right 数组中记录。当遇到一个比栈顶元素值更大的数时说明栈顶元素右边的节点已经找到更新相应索引并将栈顶元素出栈直到栈为空或遇到比当前元素小的值。这保证了栈中元素按照最大二叉树的右边界逆序排列。 构建最大二叉树 根据 left 和 right 数组以及栈中元素的关系第二次遍历数组为每个节点分配左右子树。这里通过判断条件确定当前节点应作为其父节点的左子树还是右子树最后找到根节点其左右孩子索引均为 -1。 返回根节点构建完成后返回 root即整个最大二叉树的根节点。
这种方法避免了递归调用利用栈和两次遍历数组的方式实现了从给定数组直接构建最大二叉树的功能时间复杂度为 O(n)空间复杂度也为 O(n)。
617. 合并二叉树 方法一深度优先搜索
class Solution {public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {if (t1 null) {return t2;}if (t2 null) {return t1;}TreeNode merged new TreeNode(t1.val t2.val);merged.left mergeTrees(t1.left, t2.left);merged.right mergeTrees(t1.right, t2.right);return merged;}
}这段代码定义了一个名为 Solution 的类其中包含一个方法 mergeTrees用于合并两棵二叉树 t1 和 t2。合并规则是如果两个节点重叠那么它们的值相加作为新节点的值非空节点与空节点相遇时非空节点将被保留。该方法递归地实现了这一过程具体步骤如下 基本情况检查 首先如果 t1 为空直接返回 t2表示当前子树以 t2 为准。如果 t2 为空直接返回 t1表示当前子树以 t1 为准。 创建合并节点 如果两个节点都不为空创建一个新的 TreeNode其值为 t1.val t2.val这表示合并了两个节点的值。 递归合并子树 对于新节点的左子树递归调用 mergeTrees(t1.left, t2.left)将 t1 和 t2 的左子树合并并将结果赋给新节点的左子指针。对于新节点的右子树递归调用 mergeTrees(t1.right, t2.right)将 t1 和 t2 的右子树合并并将结果赋给新节点的右子指针。 返回合并后的节点 最终返回新创建的合并节点这样就完成了从当前节点开始的整个子树的合并。
通过这样的递归处理整棵树被自顶向下地合并直至所有节点都被正确处理最终返回合并后树的根节点。这种方法简洁而高效适合解决这类二叉树合并的问题。
方法二广度优先搜索
class Solution {public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {if (t1 null) {return t2;}if (t2 null) {return t1;}TreeNode merged new TreeNode(t1.val t2.val);QueueTreeNode queue new LinkedListTreeNode();QueueTreeNode queue1 new LinkedListTreeNode();QueueTreeNode queue2 new LinkedListTreeNode();queue.offer(merged);queue1.offer(t1);queue2.offer(t2);while (!queue1.isEmpty() !queue2.isEmpty()) {TreeNode node queue.poll(), node1 queue1.poll(), node2 queue2.poll();TreeNode left1 node1.left, left2 node2.left, right1 node1.right, right2 node2.right;if (left1 ! null || left2 ! null) {if (left1 ! null left2 ! null) {TreeNode left new TreeNode(left1.val left2.val);node.left left;queue.offer(left);queue1.offer(left1);queue2.offer(left2);} else if (left1 ! null) {node.left left1;} else if (left2 ! null) {node.left left2;}}if (right1 ! null || right2 ! null) {if (right1 ! null right2 ! null) {TreeNode right new TreeNode(right1.val right2.val);node.right right;queue.offer(right);queue1.offer(right1);queue2.offer(right2);} else if (right1 ! null) {node.right right1;} else {node.right right2;}}}return merged;}
}这段代码同样定义了一个名为 Solution 的类其中的 mergeTrees 方法用于合并两棵二叉树 t1 和 t2但与之前的递归解法不同这里采用的是广度优先搜索BFS的方法。具体步骤如下 基本情况检查 首先检查 t1 和 t2 是否为空与之前一样如果一方为空则直接返回另一方。 初始化合并后的树 创建一个新的树节点 merged其值为 t1.val t2.val。 初始化队列 定义三个队列分别用于存储当前层待处理的合并后节点、t1 的节点和 t2 的节点。初始时将 merged 及其对应的 t1 和 t2 根节点分别加入各自的队列。 广度优先遍历并合并 使用 while 循环处理队列直到 queue1 和 queue2 都为空。每次循环从队列中弹出当前层的 merged 节点、t1 的节点和 t2 的节点。对于左子树和右子树如果有任何一个非空则创建或直接引用新的节点进行合并 若 t1 和 t2 的子节点都非空则创建新节点值为两个子节点的值之和然后将新节点分别加入合并后的树、queue1 和 queue2。若只有一个非空则直接将非空的子节点挂接到合并后的树上。 返回合并后的树 遍历完成后返回最初的合并节点 merged即合并后的二叉树的根节点。
这种方法通过层序遍历的方式合并两棵树同样能有效地合并两棵二叉树但相比于递归解法它在处理大量树节点时可能会占用更多内存因为需要同时维护多个队列来存储每层的节点。不过它提供了一种迭代而非递归的视角来解决问题增加了算法实现的多样性。
700. 二叉搜索树中的搜索
给定二叉搜索树BST的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在则返回 null 。
方法一递归
class Solution {public TreeNode searchBST(TreeNode root, int val) {if (root null) {return null;}if (val root.val) {return root;}return searchBST(val root.val ? root.left : root.right, val);}
}
这段代码定义了一个名为 Solution 的类其中包含一个方法 searchBST。该方法在一个二叉搜索树BST中查找值为 val 的节点并返回找到的节点。如果没有找到则返回 null。方法使用了递归的方式来实现搜索逻辑。下面是详细的步骤解释 基本情况检查首先检查当前节点 root 是否为空。如果为空说明树中没有找到值为 val 的节点因此返回 null。 匹配节点值接下来比较当前节点 root 的值与其要查找的值 val。如果两者相等即找到了目标节点直接返回当前节点 root。 选择递归方向如果当前节点的值不等于 val则根据 BST 的性质左子树所有节点的值小于根节点右子树所有节点的值大于根节点决定下一步搜索的方向 如果 val 小于当前节点值 root.val则向左子树 (root.left) 继续搜索。如果 val 大于当前节点值 root.val则向右子树 (root.right) 继续搜索。 这里使用了条件运算符三元运算符来简洁地表达这一选择逻辑。 递归调用根据选择的方向递归调用 searchBST 方法并将搜索结果返回。由于每次递归调用都更接近目标值或最终确定目标不存在当遇到空节点时因此这个过程是逐步缩小搜索范围直至找到目标或遍历完可能的路径。
通过上述递归过程该方法能够高效地在二叉搜索树中查找指定值的节点。
方法二迭代
class Solution {public TreeNode searchBST(TreeNode root, int val) {while (root ! null) {if (val root.val) {return root;}root val root.val ? root.left : root.right;}return null;}
}
这段代码同样定义了一个名为 Solution 的类其中包含一个方法 searchBST用于在一个二叉搜索树BST中查找值为 val 的节点。与之前的递归实现不同这里采用的是迭代方法来遍历树并查找目标节点。下面是该方法的详细解释 循环条件与初始化使用一个 while 循环来遍历树直到找到目标节点或遍历完整个树即 root 变为 null。 查找并返回匹配节点在循环体内首先检查当前节点 root 的值是否等于 val。如果相等说明找到了目标节点直接返回该节点。 决定遍历方向如果当前节点的值不等于 val根据二叉搜索树的性质选择遍历方向 如果 val 小于当前节点值 root.val则向左子树移动即令 root root.left。如果 val 大于当前节点值 root.val则向右子树移动即令 root root.right。 循环结束如果循环结束时仍未找到匹配的节点即 root 变为 null则返回 null表示树中不存在值为 val 的节点。
通过这样的迭代过程该方法能够高效地在二叉搜索树中查找指定值的节点且相比递归实现它在某些情况下尤其是树深度大时可以减少调用栈的空间消耗。
98. 验证二叉搜索树
给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下
节点的左 子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
方法一: 递归
class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean isValidBST(TreeNode node, long lower, long upper) {if (node null) {return true;}if (node.val lower || node.val upper) {return false;}return isValidBST(node.left, lower, node.val) isValidBST(node.right, node.val, upper);}
}这段代码定义了一个名为 Solution 的类其中包含一个公共方法 isValidBST 用于检查给定的二叉树是否是一棵有效的二叉搜索树BST。二叉搜索树的特性是对于任意节点其左子树中所有节点的值都严格小于该节点的值其右子树中所有节点的值都严格大于该节点的值。此外还定义了一个重载的辅助方法 isValidBST用于递归校验每个节点是否满足BST的条件并且传递了当前节点值允许的最小值 lower 和最大值 upper 作为边界条件。
具体逻辑如下 公共方法 isValidBST这是用户调用的接口接收树的根节点 root 作为参数。它通过调用重载的辅助方法 isValidBST 来进行实际的验证工作初始化 lower 为 Long.MIN_VALUEJava中的最小长整型值确保任何合法节点值都大于它upper 为 Long.MAX_VALUEJava中的最大长整型值确保任何合法节点值都小于它。 辅助方法 isValidBST 基本情况如果当前节点 node 为空说明已遍历到树的底部返回 true 表示这一分支是有效的。检查节点值如果当前节点的值不在允许的范围内即 node.val lower 或 node.val upper说明违反了BST的规则返回 false。递归验证对当前节点的左子树和右子树进行递归验证。左子树的每个节点值必须小于当前节点值因此传递当前节点值作为下一次递归的上限 uppernode.val右子树的每个节点值必须大于当前节点值所以传递当前节点值作为下一次递归的下限 lowernode.val。只有当左右子树都满足BST条件时整个树才被认为是有效的BST因此这里使用逻辑与操作 连接两个递归调用的结果。
通过这样的递归策略代码能够高效地遍历整个二叉树同时在每个递归层级上检查节点值是否满足BST的定义从而确定给定的二叉树是否是一个有效的二叉搜索树。
方法二中序遍历
class Solution {public boolean isValidBST(TreeNode root) {DequeTreeNode stack new LinkedListTreeNode();double inorder -Double.MAX_VALUE;while (!stack.isEmpty() || root ! null) {while (root ! null) {stack.push(root);root root.left;}root stack.pop();// 如果中序遍历得到的节点的值小于等于前一个 inorder说明不是二叉搜索树if (root.val inorder) {return false;}inorder root.val;root root.right;}return true;}
}这段代码定义了一个名为 Solution 的类其中包含一个公共方法 isValidBST用于判断给定的二叉树是否为有效的二叉搜索树BST。与之前的递归解法不同这里采用迭代方法利用栈来实现中序遍历。下面是代码的详细解析 初始化声明一个 Deque双端队列stack 用于存放待访问的节点以及一个 double 类型的变量 inorder 初始化为负无穷大用于存储中序遍历过程中访问过的节点值用于检查BST性质。 迭代遍历使用一个 while 循环条件为栈非空或当前根节点 root 非空确保遍历完整个二叉树。 左子树入栈在循环内部首先不断将当前节点 root 的左子节点压入栈中直到没有左子节点这步是为了确保每次处理的节点都是当前子树的最左节点即中序遍历的顺序。 处理当前节点当左子节点为空时从栈顶弹出节点作为当前节点 root并检查其值是否大于 inorder。如果不大于即小于等于说明违背了BST的性质中序遍历下严格递增直接返回 false。 更新 inorder如果当前节点值符合BST性质则更新 inorder 为当前节点值准备与下一个节点比较。 转向右子树最后将当前节点更新为其右子节点继续遍历。 遍历结束判断当遍历完整个树栈为空且当前 root 也为空后说明所有节点都满足BST的条件返回 true。
这种方法通过迭代实现了二叉树的中序遍历并在遍历过程中实时检查每个节点的值是否满足BST的定义是一种空间效率较高的算法因为它只需要常数级别的额外空间除了存储树本身的栈空间。
