題目簡介
104.二叉樹的最大深度
給定一個(gè)二叉樹 root ，返回其最大深度。
二叉樹的 最大深度 是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。
559.n叉樹的最大深度
給定一個(gè) N 叉樹，找到其最大深度。
最大深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)總數(shù)。
N 叉樹輸入按層序遍歷序列化表示，每組子節(jié)點(diǎn)由空值分隔（請參見示例）。
111.二叉樹的最小深度
給定一個(gè)二叉樹，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說明：葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
222.完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)
給你一棵** 完全二叉樹** 的根節(jié)點(diǎn) root ，求出該樹的節(jié)點(diǎn)個(gè)數(shù)。
完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節(jié)點(diǎn)可能沒填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~ 2<sup>h</sup> 個(gè)節(jié)點(diǎn)。
初見思路
- 遞歸法，很直觀；如果想要用迭代法解，可以考慮用層序遍歷。
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1
- 層序每層遞歸尋找子節(jié)點(diǎn)最大的深度即可。層序遍歷遞歸比較類似，閑著可以寫一下。
class Solution:
def maxDepth(self, root: 'Node') -> int:
if not root:
return 0
depth = 0
for i in range(len(root.children)):
depth = max(depth, self.maxDepth(root.children[i]))
return depth + 1
- 迭代法即可，有一個(gè)坑是要考慮根節(jié)點(diǎn)一邊為空的極端情況。
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
# 極端情況
if (not root.left) and root.right:
return self.minDepth(root.right) + 1
if root.left and (not root.right):
return self.minDepth(root.left) + 1
return min(self.minDepth(root.left),self.minDepth(root.right)) + 1
- 直接層序遍歷
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = collections.deque([root])
node_cnt = 0
while queue:
size = len(queue)
node_cnt += size
for _ in range(size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return node_cnt
復(fù)盤思路
重點(diǎn)難點(diǎn)
無
今日收獲
- 二叉樹相關(guān)特性
