Dfs

Intuition Use recursion to traverse the tree, always returning the max value of the right and left tree. Approach Complexity Time complexity: O(n) Space complexity: O(log(n)), in case the tree is balanced Code # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def maxDepth(self, root): """ :type root: Optional[TreeNode] :rtype: int """ return self.maxD(root, 0) def maxD(self, root, level): if not root: return level return max(self.maxD(root.left, level+1),self.maxD(root.right, level+1))

Intuition Check all items simultaneosly Approach Complexity Time complexity: O(n) Space complexity: O(1) Code # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSameTree(self, p, q): """ :type p: Optional[TreeNode] :type q: Optional[TreeNode] :rtype: bool """ if not p and not q: return True if not p or not q: return False if p.val != q.val: return False return self.isSameTree(p.right, q.right) and self.isSameTree(p.left, q.left)