21天养成编程习惯：Leetcode刷题第Day04天

火币app官网下载 2022年10月21日 11:02 49 Connor

「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入，如果加入了之前的社群不需要重复加入。进群之后大家可以参与每周日晚20:00的升级打怪活动以及每个月的青少年编程组队学习活动。

本期训练营根据孩子们对知识的掌握情况分成两个打卡群（Leetcode简单打卡群、Leetcode中等打卡群），每个打卡群针对不同需求的孩子，这就使得本次活动更具有针对性，对孩子学习编程帮助更大。

活动的时间从10月1日至10月21日，每天一道编程题。

参与的小朋友可以，让他邀请你到本次相应的打卡群并把本次的打卡题目发给你。

微信号：ProgrammingAssistant

Day04： 108_将有序数组转换为二叉搜索树

难度：简单

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例1:

展开全文

输入：nums = [ -10, -3, 0, 5, 9]

输出：[ 0, -3, 9, -10,null, 5]

解释：[ 0, -10, 5,null, -3,null, 9] 也将被视为正确答案：

示例2:

输入：nums = [ 1, 3]

输出：[ 3, 1]

解释：[ 1,null, 3] 和 [ 3, 1] 都是高度平衡二叉搜索树。

提示：

nums 按严格递增顺序排列

C#语言

* Definition for a binary tree node.

* public class TreeNode

* public int val;

* public TreeNode left;

* public TreeNode right;

* public TreeNode(int x) { val = x; }

publicclassSolution

publicTreeNode SortedArrayToBST( int[] nums)

returnnums == null? null: BuildTree(nums, 0, nums.Length - 1);

privateTreeNode BuildTree( int[] nums, intleft, intright)

if(left > right)

returnnull;

intmid = left + (right - left)/ 2;

TreeNode root = newTreeNode(nums[mid]);

root.left = BuildTree(nums, left, mid - 1);

root.right = BuildTree(nums, mid + 1, right);

returnroot;

Python语言

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

classSolution(object):

defsortedArrayToBST(self, nums):

:type nums: List[int]

:rtype: TreeNode

returnNoneifnums isNoneelseself.BuildTree(nums, 0, len(nums) - 1)

defBuildTree(self, nums, left, right):

ifleft > right:

returnNone

mid = left + (right - left) // 2

root = TreeNode(nums[mid])

root.left = self.BuildTree(nums, left, mid - 1)

root.right = self.BuildTree(nums, mid + 1, right)

returnroot

Day04：95_不同的二叉搜索树II

难度：中等

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树。可以按任意顺序返回答案。

示例1：

输入：n = 3

输出：[[ 1,null, 2,null, 3],[ 1,null, 3, 2],[ 2, 1, 3],[ 3, 1,null,null, 2],[ 3, 2,null, 1]]

示例2：

输入：n = 1

输出：[[ 1]]

提示：

1 <= n <= 8

思路：递归。

如果将 i 作为根节点，那么 [1, i-1] 为 i 的左子树节点， [i+1, n] 为右子树节点。

问题就被拆分为两个子问题了：

求左区间构成的所有二叉搜索树作为 i 的左子树

求右区间构成的所有二叉搜索树作为 i 的右子树

求左区间构成的所有二叉搜索树作为 i 的左子树

求右区间构成的所有二叉搜索树作为 i 的右子树

递归终止条件：

区间为空，返回null。

区间的左右端点相同，即只包含一个数，返回该数构成的根结点。

区间为空，返回null。

区间的左右端点相同，即只包含一个数，返回该数构成的根结点。

以上就是利用递归求解该问题的思路。

C# 语言

* Definition for a binary tree node.

* public class TreeNode {

* public int val;

* public TreeNode left;

* public TreeNode right;

* public TreeNode(int x) { val = x; }

publicclassSolution

publicIList<TreeNode> GenerateTrees( intn)

if(n == 0)

returnnewList<TreeNode>;

returnGenerateTrees( 1, n);

publicList<TreeNode> GenerateTrees( intstart, intend)

List<TreeNode> lst = newList<TreeNode>;

//此时没有数字，将 null 加入结果中

if(start > end)

lst.Add( null);

returnlst;

//只有一个数字，当前数字作为一棵树加入结果中

if(start == end)

TreeNode tree = newTreeNode(start);

lst.Add(tree);

returnlst;

//尝试每个数字作为根节点

for( inti = start; i <= end; i++)

//得到所有可能的左子树

List<TreeNode> leftTrees = GenerateTrees(start, i - 1);

//得到所有可能的右子树

List<TreeNode> rightTrees = GenerateTrees(i + 1, end);

//左子树右子树两两组合

foreach (TreeNode leftTree in leftTrees)

foreach (TreeNode rightTree in rightTrees)

TreeNode root = newTreeNode(i);

root.left = leftTree;

root.right = rightTree;

//加入到最终结果中

lst.Add(root);

returnlst;

Python 语言

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

classSolution(object):

defgenerateTrees(self, n):

:type n: int

:rtype: List[TreeNode]

ifn == 0:

returnlist

returnself.generate( 1, n)

defgenerate(self, start, end):

lst = list

ifstart > end:

lst.append( None)

returnlst

ifstart == end:

tree = TreeNode(start)

lst.append(tree)

returnlst

fori inrange(start, end + 1):

leftTrees = self.generate(start, i - 1)

rightTrees = self.generate(i + 1, end)

forleftTree inleftTrees:

forrightTree inrightTrees:

tree = TreeNode(i)

tree.left = leftTree

tree.right = rightTree

lst.append(tree)

returnlst

青少年编程升级打怪计划

把电子学会的青少年编程能力等级测评作为游戏的关卡，带着小朋友们升级打怪。

每周日晚20:00，利用腾讯会议进行直播分享，之后安排一个测试（与等级测评的题目数量一致）考察小朋友们对知识的掌握情况。

为了，让各个阶段的小朋友都能参与到学习中，我们每个月都会组织Scratch、Python、C++的青少年编程学习活动，为小朋友们三助力，即学习编程助力、实践知识助力、结识伙伴助力。

一键三连，一起学习⬇️

C# 多线程ThreadPool用法举例

盟可睐Moncler成都远洋太古里旗舰店隆重揭幕

发表评论

21天养成编程习惯：Leetcode刷题第Day04天

C# 多线程ThreadPool用法举例

盟可睐Moncler成都远洋太古里旗舰店隆重揭幕

最新留言

标签列表