104. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

\

DFS 解法

My Solution:

• 经典题目

• 如果Node为空返回0

• 唯一要注意的是，在class Solution里面，self指的是Solution这个class里的一个object

• Time complexity: O(n)

  n is the total number of nodes in the binary tree.

• Space complexity: O(h)

  h is the height of the binary tree. but in the worst case, it can be as large as O(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 maxDepth(self, root: Optional[TreeNode]) -> int:
				if not root:
						return 0
				return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

BFS解法

Solution:

• Time complexity: O(n)

  n is the total number of nodes in the binary tree.

• Space complexity: O(w)

  w is the maximum width of the tree (worst-case O(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 maxDepth(self, root: Optional[TreeNode]) -> int:
		    if not root:
				    return 0
				q = deque()
				q.append(root)
				
				depth = 0
				while q:
						depth += 1
						
						for _ in range(len(q)):
								node = q.popleft()
								if node.left:
										q.append(node.left)
								if node.right:
										q.append(node.right)
										
			  return depth

100. Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.