medium
Question
二叉树的右节点要么是拥有姊妹节点的叶节点，要么是空。将二叉树上下颠倒，原来的右节点成为新树的左叶节点。新树的根节点是什么？
Example:
Given a binary tree {1,2,3,4,5},
1
/ \
2 3
/ \
4 5
return the root of the binary tree [4,5,2,#,#,3,1].
4
/ \
5 2
/ \
3 1
Solution
p.left = parent.right
p.right = parent
Top-down Approach
# 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 maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
p, parent, parentRight = root, None, None
while p != None:
left = p.left
p.left = parentRight
parentRight = p.right
p.right = parent
parent = p
p = left
return parent
Bottom-up Approach
# 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 maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
return self.dfsBottomUp(root, None)
def dfsBottomUp(self, p, parent):
if p == None:
return parent
root = self.dfsBottomUp(p.left, p)
p.left = parent if parent == None else parent.right
p.right = parent
return root
