問(wèn)題描述：【Tree】429. N-ary Tree Level Order Traversal
解題思路：
這道題是給一棵 N 叉樹(shù)，層次遍歷將每一層的結(jié)點(diǎn)保存在列表中笼沥。
層次遍歷就是使用隊(duì)列蚪燕，將每一層的地址和層數(shù)保存在隊(duì)列中即可。
Python3 實(shí)現(xiàn)：
"""
# 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: # 隊(duì)列不為空奔浅，一直遍歷到為空
ans.append([])
while q and q[0][1] == deep: # 相同層
addr = q.popleft()[0] # 取該層根結(jié)點(diǎn)地址
ans[-1].append(addr.val)
for child in addr.children: # 將根結(jié)點(diǎn)的孩子放入隊(duì)列
q.append((child, deep + 1))
deep += 1 # 層數(shù)加1
return ans
問(wèn)題描述：【Tree】559. Maximum Depth of N-ary Tree
解題思路：
這道題是給一個(gè) N 叉樹(shù)馆纳，求最大深度。
二叉樹(shù)的最大深度為 max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1汹桦，拓展到 N 叉樹(shù)鲁驶，只需要對(duì)于 root.children 的每一個(gè)孩子 child （for child in root.children），更新最大深度 ans = max(ans, self.maxDepth(child))舞骆，最后 ans + 1 就是答案钥弯。
Python3 實(shí)現(xiàn)：
"""
# 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
問(wèn)題描述：【Tree】589. N-ary Tree Preorder Traversal
解題思路：
這道題是給一個(gè) N 叉樹(shù)，將前序遍歷的結(jié)果保存在列表中葛作。
前序遍歷：先保存根寿羞，再遞歸孩子 child（for child in root.children）猖凛。
Python3 實(shí)現(xiàn)：
"""
# Definition for a Node.
class Node:
def __init__(self, val, children):
self.val = val
self.children = children # root.children 是以列表的形式存儲(chǔ)的
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
self.ans = [] # 比將 ans 作為參數(shù)傳入的效率高一些
self.dfs(root)
return self.ans
def dfs(self, root):
if root:
self.ans.append(root.val)
for child in root.children: # root.children 是以列表的形式存儲(chǔ)的
self.dfs(child)
問(wèn)題描述：【Tree】590. N-ary Tree Postorder Traversal
解題思路：
這道題是給一個(gè) N 叉樹(shù)赂蠢，將后序遍歷的結(jié)果保存在列表中。
思路同上面的 Leetcode 589辨泳。后序遍歷：先遞歸孩子 child（for child in root.children）虱岂，再保存根。
Ptthon3 實(shí)現(xiàn)：
"""
# Definition for a Node.
class Node:
def __init__(self, val, children):
self.val = val
self.children = children # root.children 是以列表的形式存儲(chǔ)的
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
self.ans = [] # 比將 ans 作為參數(shù)傳入的效率高一些
self.dfs(root)
return self.ans
def dfs(self, root):
if not root:
return
for child in root.children: # root.children 是以列表的形式存儲(chǔ)的
self.dfs(child)
self.ans.append(root.val)
問(wèn)題描述：【Tree】669. Trim a Binary Search Tree
解題思路：
這道題是給一棵二叉搜索樹(shù)和一個(gè)區(qū)間 [L,R]菠红，通過(guò)修剪這棵樹(shù)第岖，使得所有結(jié)點(diǎn)的值在 [L,R] 中 (R>=L) 。
- 當(dāng) root 的值位于 L 和 R 之間试溯，則遞歸修剪其左右子樹(shù)蔑滓，返回 root。
- 當(dāng) root 的值小于 L遇绞，則其左子樹(shù)的值都小于 L键袱，拋棄左子樹(shù)，返回修剪過(guò)的右子樹(shù)摹闽。
- 當(dāng) root 的值大于 R蹄咖，則其右子樹(shù)的值都大于 R，拋棄右子樹(shù)付鹿，返回修剪過(guò)的左子樹(shù)澜汤。
遞歸的思想就在于我們不用管遞歸內(nèi)部怎么實(shí)現(xiàn)的蚜迅，我們只需要知道遞歸函數(shù)可以完成某種操作，遞歸真正需要關(guān)注的是遞歸的出口和返回值俊抵。因此這道題我們可以想象 self.trimBST(root.right, L, R) 就能修建完右子樹(shù)并返回修剪好的根結(jié)點(diǎn)谁不，同理 self.trimBST(root.left, L, R) 就能修建完左子樹(shù)并返回修剪好的根結(jié)點(diǎn)。
Python3 實(shí)現(xiàn)：
# 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: # 拋棄左子樹(shù)徽诲，返回修剪過(guò)的右子樹(shù)
return self.trimBST(root.right, L, R)
if root.val > R: # 拋棄右子樹(shù)拍谐，返回修剪過(guò)的左子樹(shù)
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
