medium

Question

二叉樹的右節(jié)點(diǎn)要么是擁有姊妹節(jié)點(diǎn)的葉節(jié)點(diǎn)，要么是空。將二叉樹上下顛倒，原來的右節(jié)點(diǎn)成為新樹的左葉節(jié)點(diǎn)。新樹的根節(jié)點(diǎn)是什么？

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