[LeetCode]—— 226——翻转二叉树

小李很执着

发布于 2024-06-15 09:03:42

780

发布于 2024-06-15 09:03:42

文章被收录于专栏：学习笔记学习笔记

1.题目

. - 力扣（LeetCode）

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

2.解答

一开始翻转第二层的，他们的子树跟着过去，相当于翻转下一层的一半，就像一个数组，我们对其进行二分翻转，第一次找到中间位置，把数组分为两个部分，然后翻转，之后把左右部分接着在里面分成两个部分，对应着左右子树，翻转，直至翻转到最后只有两个元素组成的部分，翻转结束

2.代码实现分析

函数的输入是一个指向根节点的指针，输出是翻转后的二叉树的根节点指针。首先，检查根节点是否为空。如果为空，直接返回根节点。然后，将根节点的左子树和右子树进行交换。这可以通过创建一个临时指针来完成，将左子树指针的值赋给它，然后将左子树指针指向右子树，再将右子树指针指向临时指针。接下来，递归地对左子树和右子树进行翻转。这样可以确保所有的子树都被翻转。最后，返回翻转后的根节点。该代码的时间复杂度是O(n)，其中n是树中节点的个数。因为每个节点都被访问一次。总结：该代码使用递归的方式翻转了二叉树。递归的思想是先处理当前节点，然后递归地处理其左子树和右子树。通过不断交换左子树和右子树，最终完成翻转。

3.代码实现：

1.前序

struct TreeNode* invertTree(struct TreeNode* root){
    if(root == NULL)
        return root;
    struct TreeNode* temp= root->left;;
    root->left = root->right;
    root->right = temp;
    invertTree(root->left);         
    invertTree(root->right);        
    return root;
}

2.后序

struct TreeNode* invertTree(struct TreeNode* root){
    if(root == NULL)
        return root;
   
    invertTree(root->left);         
    invertTree(root->right);  
     struct TreeNode* temp= root->left;;
    root->left = root->right;
    root->right = temp;      
    return root;
}

3.中序

struct TreeNode* invertTree(struct TreeNode* root){
    if(root == NULL)
        return root;
    invertTree(root->left);  
      struct TreeNode* temp= root->left;;
    root->left = root->right;
    root->right = temp;           
    invertTree(root->left);  
     
    return root;
}