【Leetcode】543. Diameter of Binary Tree解题报告
求二叉树最大直径
方法1 递归法
class Solution1(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res = 0
self.DFS(root)
return self.res
def DFS(self,root):
if root == None:
return 0
l = self.DFS(root.left)
r = self.DFS(root.right)
self.res = max(self.res, l + r )
return max(l, r) +1
方法2 后续非递归
后续非递归遍历加dict保存每个节点的最大深度
因为每个节点只有遍历完其左子树和右子树后才能获得其最大深度,所以得postorder
class Solution2(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
from collections import defaultdict
dictionary = defaultdict(int)
stack, pNode, prev,res = [], root, None,0
while(len(stack) or pNode):
if pNode:
stack.append(pNode)
pNode = pNode.left
else:
pNode = stack[-1]
if pNode.right == None or pNode.right == prev:
curr_path = dictionary[pNode.left] + dictionary[pNode.right]
res = max(res, curr_path)
dictionary[pNode] = max(dictionary[pNode.left], dictionary[pNode.right]) + 1
prev = pNode
pNode = None
stack.pop()
else:
pNode = pNode.right
return res