```
head = root
mem = 0
s = []
while s or root:
if s:
root = s.pop()
root.left, root.right = root.right, root.left
if root.left:
s.append(root.left)
if root.right:
s.append(root.right)
root = None
s = []
root = head
while s or root:
while root:
s.append(root)
root = root.left
root = s.pop()
root.val += mem
mem = root.val
root = root.right
s = []
root = head
while s or root:
if s:
root = s.pop()
root.left, root.right = root.right, root.left
if root.left:
s.append(root.left)
if root.right:
s.append(root.right)
root = None
return head
```