104. 二叉樹(shù)的最大深度 - 力扣（LeetCode）
image.png
解題思路
前序遍歷和后續(xù)遍歷都可以镐牺，注意區(qū)分高度和深度
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
deep_left = self.maxDepth(root.left)
deep_right = self.maxDepth(root.right)
deep = 1 + max(deep_left, deep_right)
return deep
111. 二叉樹(shù)的最小深度 - 力扣（LeetCode）
image.png
解題思路
和求最大深度差不多，注意葉子節(jié)點(diǎn)不是空
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root :
return 0
deep_left = self.minDepth(root.left)
deep_right = self.minDepth(root.right)
if root.left == None and root.right != None:
return 1 + deep_right
elif root.left != None and root.right == None:
return 1 + deep_left
return 1 + min(deep_left,deep_right)
222. 完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù) - 力扣（LeetCode）
解題思路
普通二叉樹(shù)：層序遍歷和后序遞歸魁莉；完全二叉樹(shù)：如果是滿二叉樹(shù)就可以直接利用公式計(jì)算節(jié)點(diǎn)個(gè)數(shù)睬涧，假如完全二叉樹(shù)的左右深度都一樣就是滿二叉樹(shù)。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# 遞歸法
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
c_left = self.countNodes(root.left)
c_right = self.countNodes(root.right)
return 1 + c_left + c_right
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# 層序遍歷
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
count = 0
queue = collections.deque([root])
while queue:
n = len(queue)
for _ in range(n):
cur = queue.popleft()
count += 1
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return count
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# 完全二叉樹(shù)方法 滿二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)：2^depth-1
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
left = root.left
right = root.right
left_depth = 1
right_depth = 1 #方便后續(xù)進(jìn)行位運(yùn)算旗唁，寫(xiě)0
while left: #計(jì)算左邊的深度
left = left.left
left_depth += 1
while right: # 計(jì)算右邊的深度
right = right.right
right_depth += 1
if left_depth == right_depth: #滿二叉樹(shù)
return (2 ** left_depth) - 1
left_count = self.countNodes(root.left)
right_count = self.countNodes(root.right)
count = left_count + right_count +1
return count
