# Given a binary tree where all the right nodes are either leaf nodes with a sibling# (a left node that shares the same parent node) or empty, flip it upside down and# turn it into a tree where the original right nodes turned into left leaf nodes.# Return the new root.## For 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## Definition for a binary tree nodeclassTreeNode:def__init__(self,x):self.val=xself.left=Noneself.right=NoneclassSolution:# @param root, a tree node# @return root of the upside down treedefupsideDownBinaryTree(self,root):ifnotroot:returnNoneifnotroot.left:returnrootnew=self.upsideDownBinaryTree(root.left)# 1. set left to be a new roottmp=newwhiletmp.right:# reach the most right leaf nodetmp=tmp.righttmp.right=TreeNode(root.val)# 2. right is origin root valueifroot.right:# 3. left is origin right value of roottmp.left=TreeNode(root.right.val)returnnewif__name__=='__main__':root=TreeNode(1)root.right=TreeNode(3)root.left=TreeNode(2)tmp=root.lefttmp.right=TreeNode(5)tmp.left=TreeNode(4)answer=Solution()result=answer.upsideDownBinaryTree(root)printresult.val,result.left.val,result.right.val,result.right.left.val,result.right.right.val
近期评论