LeetCode：226. Invert Binary Tree（倒转一棵二叉树）

客官°小女子只卖身不卖艺 2022-04-12 02:54 186阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。
> 
> 这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：

python实现方式1：

java实现方法2：

python实现方式2:

源码地址：

--------------------

### 题目描述： ###

翻转一棵二叉树。

输入：

4
       /   \
      2     7
     / \   / \
    1   3 6   9

输出：

4
       /   \
      7     2
     / \   / \
    9   6 3   1

来源：力扣（LeetCode）

--------------------

### java实现方法1： ###

/**
         * 反转一棵二叉树
         *
         * @param root 根节点
         * @return 反转后的二叉树
         */
        public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            return root;
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方式1： ###

def invert_tree(self, root: TreeNode) -> TreeNode:
            '''
                翻转二叉树
            Args:
                root: 根节点
            Returns:
                TreeNode
            '''
            if root == None:
                return None
            left = self.invert_tree(root.left)
            right = self.invert_tree(root.right)
            root.left = right
            root.right = left
            return root

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### java实现方法2： ###

/**
         * 反转一棵二叉树
         *
         * @param root 根节点
         * @return 反转后的二叉树
         */
        public TreeNode invertTree2(TreeNode root) {
            if (root == null) {
                return null;
            }
            LinkedList<TreeNode> list = new LinkedList<>();
            list.add(root);
            while (!list.isEmpty()) {
                TreeNode cur = list.poll();
                if (cur.left != null) {
                    list.add(cur.left);
                }
                if (cur.right != null) {
                    list.add(cur.right);
                }
                TreeNode temp = cur.right;
                cur.right = cur.left;
                cur.left = temp;
    
            }
            return root;
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方式2:  ###

def invert_tree2(self, root: TreeNode) -> TreeNode:
            '''
                翻转二叉树
            Args:
                root: 根节点
            Returns:
                TreeNode
            '''
            if root == None:
                return None
            node_list = []
            node_list.append(root)
            while len(node_list) > 0:
                cur = node_list.pop()
                if cur.left:
                    node_list.append(cur.left)
                if cur.right:
                    node_list.append(cur.right)
                temp = cur.right
                cur.right = cur.left
                cur.left = temp
            return root

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode