一、题目
解法一:迭代法
# 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: TreeNode :rtype: int """ #寻找最深的左节点 def inner_find_left(root,stack_temp): while root != None: stack_temp.append(root) root = root.left return stack_temp stack = [] stack = inner_find_left(root,stack) max_depth = 0 pre_node =None while stack: #2、判断栈中最后一个节点的右节点是否为空,如果不为空则继续向下寻找 temp = stack[-1] max_depth = max(max_depth,len(stack)) if temp.right != None and temp.right != pre_node: stack = inner_find_left(temp.right,stack) continue #3、如果最后一德节点的右子节点为空,代表不用继续往下寻找,应该弹出栈里的元素 pre_node = stack.pop(-1) return max_depth
解法二、递归法
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ return self.depth(root,0) def depth(self,root,n): if root == None: return n n += 1 return max(self.depth(root.left,n),self.depth(root.right,n))