?LeetCode刷題實(shí)戰(zhàn)156：上下翻轉(zhuǎn)二叉樹
Given a binary tree in which all right nodes are either leaf nodes with sibling nodes (left nodes with the same parent nodes) or empty, flip the binary tree up and down and turn it into a tree, and the original right nodes will be converted into left leaf nodes. Returns the new root.? ?
題意
解題
https://blog.csdn.net/qq_32424059/article/details/93920527
class?Solution(object):
????def?upsideDownBinaryTree(self, root):
????????"""
????????:type root: TreeNode
????????:rtype: TreeNode
????????"""
????????#每一個(gè)節(jié)點(diǎn)變成其左孩子的右節(jié)點(diǎn)
????????if?not?root or?(not?root.left and?not?root.right):
????????????return?root
?
????????newroot = self.upsideDownBinaryTree(root.left)
????????# self.upsideDownBinaryTree(root.right) 右孩子不用處理 因?yàn)橐床淮嬖谝词侨~節(jié)點(diǎn)
????????
????????root.left.left = root.right
????????root.left.right = root
????????root.left = None
????????root.right = None
?
????????return?newroot
class?Solution(object):
????def?upsideDownBinaryTree(self, root):
????????"""
????????:type root: TreeNode
????????:rtype: TreeNode
????????"""
????????#每一個(gè)節(jié)點(diǎn)變成其左孩子的右節(jié)點(diǎn)
????????if?not?root or?(not?root.left and?not?root.right):
????????????return?root
?
????????parent, sibling = None, None
????????while?root:
????????????tmp = root.left
????????????root.left = sibling
????????????
????????????sibling = root.right
????????????root.right = parent
????????????
????????????parent = root
????????????root = tmp
????????????
????????return?parent