xiaolei565

236. 二叉树的最近公共祖先(一般)给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 示例 1： 123输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2： 123输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出：5解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3：12输入：root = [1,2], p = 1, q = 2输出：1 提示： 树中节点数目在范围 [2, 105] 内。 -109 <= Node.val <= 109 ...

415. 字符串相加(简单)给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。 提示： num1 和num2 的长度都小于 5100 num1 和num2 都只包含数字 0-9 num1 和num2 都不包含任何前导零 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/add-strings 思路：用int会溢出，从后往前，相加，考虑进位，使用string输出 代码：1234567891011121314151617181920212223class Solution { public String addStrings(String num1, String num2) { StringBuilder res =new StringBuilder(); int len1 = num1.length(); int len2 = num2.length(); ...

25. K 个一组翻转链表(较难)给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 进阶： 你可以设计一个只使用常数额外空间的算法来解决此问题吗？你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 示例 1：输入：head = [1,2,3,4,5], k = 2输出：[2,1,4,3,5] 示例 2：输入：head = [1,2,3,4,5], k = 3输出：[3,2,1,4,5] 示例 3：输入：head = [1,2,3,4,5], k = 1输出：[1,2,3,4,5] 示例 4：输入：head = [1], k = 1输出：[1]提示： 列表中节点的数量在范围 sz 内1 <= sz <= 50000 <= Node.val <= 10001 <= k <= sz 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-nodes-in ...

129. 求根节点到叶节点数字之和(一般)给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字： 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。计算从根节点到叶节点生成的 所有数字之和 。 叶节点 是指没有子节点的节点。 示例 1： 123456输入：root = [1,2,3]输出：25解释：从根到叶子节点路径 1->2 代表数字 12从根到叶子节点路径 1->3 代表数字 13因此，数字总和 = 12 + 13 = 25 示例 2： 1234567输入：root = [4,9,0,5,1]输出：1026解释：从根到叶子节点路径 4->9->5 代表数字 495从根到叶子节点路径 4->9->1 代表数字 491从根到叶子节点路径 4->0 代表数字 40因此，数字总和 = 495 + 491 + 40 = 1026 提示：树中节点的数目在范围 [1, 100 ...

117. 填充每个节点的下一个右侧节点指针 II(一般)给定一个二叉树 123456struct Node { int val; Node *left; Node *right; Node *next;} 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。 进阶：你只能使用常量级额外空间。使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。 示例：123输入：root = [1,2,3,4,5,null,7]输出：[1,#,2,3,#,4,5,7,#]解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。 提示： 树中的节点数小于 6000-100 <= node.val <= 100 来源：力扣（LeetCode）链接：http ...

99. 恢复二叉搜索树(一般)给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？ 示例 1： 输入：root = [1,3,null,null,2]输出：[3,1,null,null,2]解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。 示例 2： 输入：root = [3,1,4,null,null,2]输出：[2,1,4,null,null,3]解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。 提示：树上节点的数目在范围 [2, 1000] 内-231= Node.val <= 231sup> - 1 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/recover-binary-search-tree著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路1：中 ...

112. 路径总和(较难)给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。 叶子节点 是指没有子节点的节点。 示例 1：输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22输出：true 示例 2：输入：root = [1,2,3], targetSum = 5输出：false 示例 3：输入：root = [1,2], targetSum = 0输出：false 提示：树中节点的数目在范围 [0, 5000] 内-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/path-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路：回溯 代码：123456789101112 ...

95. 不同的二叉搜索树 II(较难)给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。 示例 1：12输入：n = 3输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]] 示例 2：12输入：n = 1输出：[[1]] 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii 思路1：回溯思路，但是没法进行去重，需要再思考思考 思路2：递归，其实有点难想 https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/ 代码：12345678910111213141516171819202122 ...

429. N 叉树的层序遍历(一般)给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。 示例 1：123输入：root = [1,null,3,2,4,null,5,6]输出：[[1],[3,2,4],[5,6]] 示例 2：12输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]] 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal 思路：层次遍历 代码：123456789101112131415161718192021222324class Solution { List<List< ...

589. N 叉树的前序遍历(简单)给定一个 N 叉树，返回其节点值的 前序遍历 。 N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。 进阶： 递归法很简单，你可以使用迭代法完成此题吗? 示例 1：1234567输入：root = [1,null,3,2,4,null,5,6]输出：[1,3,5,6,2,4]示例 2：输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10] 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal 思路1：就是参照二叉树的前序遍历，递归方法 思路2：参考前序遍历的非递归写法 代码1：12345678910111213class Solution { ...