美文网首页
树4 反转二叉树

树4 反转二叉树

作者: 是黄小胖呀 | 来源:发表于2020-09-13 16:40 被阅读0次

翻转一棵二叉树。

示例:

输入:

    4

  /  \

  2    7

/ \  / \

1  3 6  9

输出:

    4

  /  \

  7    2

/ \  / \

9  6 3  1

第一种思路:

递归+交换左右子树+保留最初的树

代码如下:

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def invertTree(self, root: TreeNode) -> TreeNode:

        if not root:

            return root

        tmp0=root

        tmp=root.right

        root.right=root.left

        root.left=tmp

        self.invertTree(root.right)

        self.invertTree(root.left)

        return tmp0

第二种思路:迭代+深度优先,用广度优先搜索的方法来进行解题,将每一层的字数加入到stack中,然后对每一个子树的左右子树进行交换

class Solution:

    def invertTree(self, root: TreeNode) -> TreeNode:

        if not root : return 

        stack = [root]

        while stack :

            length = len(stack)

            for i in range(length):

                cur = stack.pop(0)

                cur.left,cur.right = cur.right,cur.left

                if cur.left :

                    stack.append(cur.left)

                if cur.right :

                    stack.append(cur.right)

        return root

相关文章

  • 02-13:leetcode重刷2之链表反转

    1、链表反转 2、反转二叉树 3、合并二叉树 4、对称二叉树 1、反转链表 classSolution: defr...

  • Swift-反转二叉树

    题目: 反转二叉树其实就是二叉树的镜像.4/ 2 7/ \ / 1 3 6 9to4/ ...

  • Golang反转二叉树

    反转二叉树

  • 链表和二叉树

    单向链表 链表反转 二叉树定义 1、递归中序遍历 2、迭代中序遍历 3、二叉树层序遍历 4、判断一棵树是否为平衡树...

  • 二叉树

    title: 二叉树date: 2016-08-16 14:47:21tags: 算法 二叉树 二叉树的反转

  • 二叉树遍历

    二叉树 二叉树的存储结构 前序遍历 中序遍历 后序遍历 遍历代码 反转二叉树 深入学习二叉树 二叉树-你必须要懂!...

  • lint0175. 0480.

    反转一棵二叉树 Binary Tree Paths

  • 树4 反转二叉树

    翻转一棵二叉树。 示例: 输入: 4 / \ 2 7 / \ / \ 1 3 6 9 输出...

  • 2020-10-28

    快排 链表反转 链表反转 二叉树非递归实现 按层排序 二叉树深度 合并有序数组 二分查找 有序数组 查找 楼梯问题

  • LeetCode0305

    461. 汉明距离 617. 合并二叉树 226. 翻转二叉树 104. 二叉树的最大深度 206. 反转链表 2...

网友评论

      本文标题:树4 反转二叉树

      本文链接:https://www.haomeiwen.com/subject/zannektx.html