Leetcode【429、559、589、590、669】
Leetcode【429、559、589、590、669】
echobingo
发布于 2019-10-29 17:26:22
发布于 2019-10-29 17:26:22
问题描述：【Tree】429. N-ary Tree Level Order Traversal
解题思路：
这道题是给一棵 N 叉树，层次遍历将每一层的结点保存在列表中。
层次遍历就是使用队列，将每一层的地址和层数保存在队列中即可。
Python3 实现：
"""
# Definition for a Node.
class Node:
def __init__(self, val, children):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return None
q, ans = collections.deque(), []
q.append((root, 1))
deep = 1
while q: # 队列不为空，一直遍历到为空
ans.append([])
while q and q[0][1] == deep: # 相同层
addr = q.popleft()[0] # 取该层根结点地址
ans[-1].append(addr.val)
for child in addr.children: # 将根结点的孩子放入队列
q.append((child, deep + 1))
deep += 1 # 层数加1
return ans问题描述：【Tree】559. Maximum Depth of N-ary Tree
解题思路：
这道题是给一个 N 叉树，求最大深度。
二叉树的最大深度为 max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1，拓展到 N 叉树，只需要对于 root.children 的每一个孩子 child （for child in root.children），更新最大深度 ans = max(ans, self.maxDepth(child))，最后 ans + 1 就是答案。
Python3 实现：
"""
# Definition for a Node.
class Node:
def __init__(self, val, children):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
ans = 0 # 最大深度
if not root:
return 0
for child in root.children:
ans = max(ans, self.maxDepth(child))
return ans + 1问题描述：【Tree】589. N-ary Tree Preorder Traversal
解题思路：
这道题是给一个 N 叉树，将前序遍历的结果保存在列表中。
前序遍历：先保存根，再递归孩子 child（for child in root.children）。
Python3 实现：
"""
# Definition for a Node.
class Node:
def __init__(self, val, children):
self.val = val
self.children = children # root.children 是以列表的形式存储的
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
self.ans = [] # 比将 ans 作为参数传入的效率高一些
self.dfs(root)
return self.ans
def dfs(self, root):
if root:
self.ans.append(root.val)
for child in root.children: # root.children 是以列表的形式存储的
self.dfs(child)问题描述：【Tree】590. N-ary Tree Postorder Traversal
解题思路：
这道题是给一个 N 叉树，将后序遍历的结果保存在列表中。
思路同上面的 Leetcode 589。后序遍历：先递归孩子 child（for child in root.children），再保存根。
Ptthon3 实现：
"""
# Definition for a Node.
class Node:
def __init__(self, val, children):
self.val = val
self.children = children # root.children 是以列表的形式存储的
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
self.ans = [] # 比将 ans 作为参数传入的效率高一些
self.dfs(root)
return self.ans
def dfs(self, root):
if not root:
return
for child in root.children: # root.children 是以列表的形式存储的
self.dfs(child)
self.ans.append(root.val)问题描述：【Tree】669. Trim a Binary Search Tree
解题思路：
这道题是给一棵二叉搜索树和一个区间 [L,R]，通过修剪这棵树，使得所有结点的值在 [L,R] 中 (R>=L) 。
- 当 root 的值位于 L 和 R 之间，则递归修剪其左右子树，返回 root。
- 当 root 的值小于 L，则其左子树的值都小于 L，抛弃左子树，返回修剪过的右子树。
- 当 root 的值大于 R，则其右子树的值都大于 R，抛弃右子树，返回修剪过的左子树。
递归的思想就在于我们不用管递归内部怎么实现的，我们只需要知道递归函数可以完成某种操作，递归真正需要关注的是递归的出口和返回值。因此这道题我们可以想象 self.trimBST(root.right, L, R) 就能修建完右子树并返回修剪好的根结点，同理 self.trimBST(root.left, L, R) 就能修建完左子树并返回修剪好的根结点。
Python3 实现：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
if not root:
return None
if root.val < L: # 抛弃左子树，返回修剪过的右子树
return self.trimBST(root.right, L, R)
if root.val > R: # 抛弃右子树，返回修剪过的左子树
return self.trimBST(root.left, L, R)
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
return root本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.10.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录