有一个二叉树，长这样

       1       
    /     \    
   2       3   
  / \     / \  
 4   5   6   7 
/ \ / \ / \ / \
8 9 . . . . . .

写一个函数，返回所有节点深度值的和。

其中节点深度是一个节点到根节点的距离，在这里举个例子，根节点是1 ，那么值为2 的节点到根节点的距离是1.

此时应该得到的sum的结果是16。

Solution:

可以使用一个堆栈结构，首先将根节点以及他的深度depth的键值对储存到堆栈中。

这里一个对子是一个字典对象，一个个的字典对象保存在一个stack的列表里。

首先pop出一个元素，将这个元素的深度累加到计数器中，

在字典中记录下他的两个孩子的相同信息，显然此时两个孩子的depth相对于这个节点都要+1，如此往复，直到堆栈为空。

#build tree
def nodeDepths(root):
	sum_of_depth = 0
	stack = [{"node":root,"depth":0}]
	while len(stack)>0:
		node_profile = stack.pop()
		node,depth = node_profile["node"],node_profile["depth"]
		if node is None:
			continue
		print(f"当前处理节点{node.value}")
		sum_of_depth += depth
		stack.append({"node":node.left,"depth":depth + 1})
		if node.left is not None:
			print(f"append节点{node.left.value}") 
		stack.append({"node":node.right,"depth":depth + 1})
		if node.right is not None:
			print(f"append节点{node.right.value}")

		print(stack)
	return sum_of_depth


# This is the class of the input binary tree.
class BinaryTree:
	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None
A = BinaryTree(1)
B = BinaryTree(2)
C = BinaryTree(3)
A.left = B
A.right = C
D = BinaryTree(4)
E = BinaryTree(5)
B.left = D
B.right = E
F = BinaryTree(6)
G = BinaryTree(7)
C.left = F
C.right = G
H = BinaryTree(8)
I = BinaryTree(9)
D.left = H
D.right = I

print(nodeDepths(A))
# output_array = []
# print(A.breadthFirstSearch(array = output_array))

### Time: O(v+e) v是图的顶点（vertics），e是图的edge
### Space: O(v)  v是返回的array的长度


# for index,element in enumerate(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"]):
# 	print(f"{element} = BinaryTree(\"{index+1}\")")
# que = [1,2,3,4,5]
# print(que.pop(0))

output

当前处理节点1
append节点2
append节点3
[{'node': <__main__.BinaryTree object at 0x7ffc6012fbe0>, 'depth': 1}, {'node': <__main__.BinaryTree object at 0x7ffc70125190>, 'depth': 1}]
当前处理节点3
append节点6
append节点7
[{'node': <__main__.BinaryTree object at 0x7ffc6012fbe0>, 'depth': 1}, {'node': <__main__.BinaryTree object at 0x7ffc70125370>, 'depth': 2}, {'node': <__main__.BinaryTree object at 0x7ffc701252b0>, 'depth': 2}]
当前处理节点7
[{'node': <__main__.BinaryTree object at 0x7ffc6012fbe0>, 'depth': 1}, {'node': <__main__.BinaryTree object at 0x7ffc70125370>, 'depth': 2}, {'node': None, 'depth': 3}, {'node': None, 'depth': 3}]
当前处理节点6
[{'node': <__main__.BinaryTree object at 0x7ffc6012fbe0>, 'depth': 1}, {'node': None, 'depth': 3}, {'node': None, 'depth': 3}]
当前处理节点2
append节点4
append节点5
[{'node': <__main__.BinaryTree object at 0x7ffc70125040>, 'depth': 2}, {'node': <__main__.BinaryTree object at 0x7ffc70125490>, 'depth': 2}]
当前处理节点5
[{'node': <__main__.BinaryTree object at 0x7ffc70125040>, 'depth': 2}, {'node': None, 'depth': 3}, {'node': None, 'depth': 3}]
当前处理节点4
append节点8
append节点9
[{'node': <__main__.BinaryTree object at 0x7ffc70125310>, 'depth': 3}, {'node': <__main__.BinaryTree object at 0x7ffc6013c0a0>, 'depth': 3}]
当前处理节点9
[{'node': <__main__.BinaryTree object at 0x7ffc70125310>, 'depth': 3}, {'node': None, 'depth': 4}, {'node': None, 'depth': 4}]
当前处理节点8
[{'node': None, 'depth': 4}, {'node': None, 'depth': 4}]
16
[Finished in 0.6s]

Time: O(n)

Spcae: O(height of tree)

可以看到stack需要的储存空间和数的高度一致。