Implement a stack based post order traversal and store intermediate results in dictionaries.

You can also delete the results of node.left and node.right as and when you postorder process the node in question since this means that the entire subtree rooted at node is traversed.

PS: There's probably some unnecessary stuff going on in this.

```
# 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 maxDepthAndPathLen(self, node):
max_depth = max_right = max_left = 0
max_path = max_path_left = max_path_right = 0
if node.left:
max_left, max_path_left = self.maxDepthAndPathLen(node.left)
else:
max_left = -1
if node.right:
max_right, max_path_right = self.maxDepthAndPathLen(node.right)
else:
max_right = -1
if not node.left and not node.right:
return 0, 0
max_depth = max(max_left, max_right) + 1
max_path = max(max_left + max_right + 2, max_path_left, max_path_right)
return max_depth, max_path
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
node_stack = [root]
max_depth = {}
max_path = {}
seen = set()
#max_final = -1
while node_stack:
node = node_stack.pop()
if node not in seen:
seen.add(node)
node_stack.append(node)
if node.left:
node_stack.append(node.left)
if node.right:
node_stack.append(node.right)
else:
if not node.left and not node.right:
max_depth[node] = 0
max_path[node] = 0
elif not node.left and node.right:
max_right = max_depth[node.right]
max_depth[node] = max_right + 1
max_path_right = max_path[node.right]
max_path[node] = max(max_depth[node], max_path_right)
elif node.left and not node.right:
max_left = max_depth[node.left]
max_depth[node] = max_left + 1
max_path_left = max_path[node.left]
max_path[node] = max(max_depth[node], max_path_left)
else:
max_left = max_depth[node.left]
max_right = max_depth[node.right]
max_depth[node] = max(max_left, max_right) + 1
max_path[node] = max(max_left + max_right + 2,
max_path[node.left],
max_path[node.right])
return max_path[root]
```