104.二叉树的最大深度
1、后续遍历递归法
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
left_depth = self.maxDepth(root.left) # 左
right_depth = self.maxDepth(root.right) # 右
max_depth = 1 + max(left_depth, right_depth) # 中
return max_depth
2、层序遍历迭代法
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
depth = 0
queue = [root]
while queue:
n = len(queue)
depth += 1
for i in range(n):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
111.二叉树的最小深度
注意和最大深度的区别，什么条件下是最小深度
1、递归法
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
left = self.minDepth(root.left) # 左
right = self.minDepth(root.right) # 右
if root.left is None and root.right:
return 1 + right
if root.right is None and root.left:
return 1 + left
min_depth = 1 + min(left, right) # 中
return min_depth
2、层序遍历
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
queue = [root]
depth = 0
while queue:
n = len(queue)
depth += 1
for i in range(n):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not node.left and not node.right:
return depth
return depth
222.完全二叉树的节点个数
1、递归法
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
left = self.countNodes(root.left)
right = self.countNodes(root.right)
return 1 + left + right
2、层序遍历
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
queue = [root]
count = 0
while queue:
n = len(queue)
count += n
for _ in range(n):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return count
3、利用完全二叉树的特性
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
count = 1
left, right = root.left, root.right
while left and right:
count += 1
left, right = left.left, right.right
if not left and not right: # 如果同时到底说明是满二叉树，反之则不是
return 2 ** count - 1
else:
return 1 + self.countNodes(root.left) + self.countNodes(root.right)