python实现leetcode之156. 上下翻转二叉树

解题思路

先找到最左节点「最左节点是返回值」，并记住最左节点的路径
从记住的路径中取出一个节点，那个节点是前一节点的父节点，他还有一个右孩子
然后将这个父节点变为前一节点的右节点
将这个右孩子变为前一节点的左孩子
当前节点前进到这个父节点然后继续直到第一步记住的路径空

156. 上下翻转二叉树

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        return swip(root)

def swip(tree):
    if not tree: return None
    path = []
    while tree.left:
        path.append(tree)
        tree = tree.left
    # 现在tree没有left
    left_most = tree
    while path:
        parent = path.pop()
        right = parent.right
        parent.left = parent.right = None
        tree.left = right
        tree.right = parent
        tree = parent
    return left_most