Leetcode【429、559、589、590、669】
- 2019 年 10 月 29 日
- 笔记
问题描述：【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
