Most commonly used tree traversal algorithms use O(h) space, with h the height of the tree. By applying Morris algorithm, it allows to traverse a tree with O(1) space. Below is an inorder traversal algorithm which adds up the value of all the leaf nodes.
Given a binary tree, find the sum of all leaf nodes.
# Morris inorder
class Solution:
"""
@param root:
@return: the sum of leafnode
"""
def sumLeafNode(self, root):
res = 0
p = root
while p:
if p.left is None:
if p.right is None: # p is a leaf node
res += p.val
p = p.right
else:
tmp = p.left
while tmp.right is not None and tmp.right != p:
tmp = tmp.right
if tmp.right is None:
if tmp.left is None: # tmp is a leaf node
res += tmp.val
tmp.right = p
p = p.left
else:
tmp.right = None
p = p.right
return res