专栏首页weixuqin 的专栏leecode刷题(24)-- 翻转二叉树

leecode刷题(24)-- 翻转二叉树

leecode刷题(24)-- 翻转二叉树

翻转二叉树

翻转一棵二叉树。

示例:

输入:

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

输出:

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

备注: 这个问题是受到 Max Howell原问题 启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。


思路

二叉树问题,我们首先要想到的使用递归的方式来解决,有了这个思路,处理这道问题就很简单了:先互换根节点的左右节点,然后递归地处理左子树,再递归地处理右子树,直到所有的节点互换完,最后我们把 root 返回,这样便完成了二叉树的反转。

代码如下

Java描述:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root != null) {
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            
            invertTree(root.left);
            invertTree(root.right);
        }
        return root;
    }
}

最近在复习python,这里也写一下python描述:

# 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 root:
            root.left, root.right = root.right, root.left

            self.invertTree(root.left)
            self.invertTree(root.right)

        return root

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leecode刷题(6)-- 两个数组的交集II

    我们可以用遍历穷举的方法,但是时间复杂度肯定很高。不妨换个思路:先将数组递增排序,排序之后将两个数组同时遍历(定义两个数组的脚本变量,初始值为0,向后遍历),比...

    希希里之海
  • 使用代理爬取微信文章

    希希里之海
  • leecode刷题(29)-- 二叉树的中序遍历

    希希里之海
  • 【LeetCode】一文详解二叉树的三大遍历:前序、中序和后序(python和C++实现)

    深度学习技术前沿公众号博主
  • BST & AVL 二分搜索树 & 平衡二叉树的实现原理

    本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

    大学里的混子
  • 【leetcode刷题】T129-翻转二叉树

    https://leetcode-cn.com/problems/invert-binary-tree/

    木又AI帮
  • leetcode226——翻转二叉树

    故事尾音
  • 二叉树高频题

    Given a binary tree, return the preorder traversal of its nodes' values.

    用户5934629
  • LeetCode 783 & 530 Distance Between BST Nodes

    Given a Binary Search Tree (BST) with the root node root, return the minimum dif...

    大学里的混子
  • 如何使用CP / SCP / RSYNC在Linux中排除特定目录?

    对于任何系统管理员或一般Linux操作系统用户而言,在服务器之间执行文件复制操作都是一项常见任务。在将文件从一个系统复制到另一个系统时,由于某些特定原因,我们可...

    用户6543014

扫码关注云+社区

领取腾讯云代金券