【前言】

今天是力扣打卡第17天！

emmm...突然不知道说啥，上菜吧。

原题：翻转二叉树

题目描述：

翻转一棵二叉树。

示例：

输入：

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

输出：

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

题解：

方法一比较简单，都在代码里啦。

方法二：

这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以root 为根节点的整棵子树的翻转。

代码执行：

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for a binary tree node.
     
    
   

    

     

    
    

     

       * struct TreeNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * struct TreeNode *left;
     
    
   

    

     

    
    

     

       * struct TreeNode *right;
     
    
   

    

     

    
    

     

       * };
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      struct TreeNode* invertTree(struct TreeNode* root){
     
    
   

    

     

    
    

     
    //方法一
     
    
   

    

     

    
    

     
    // //找边界
     
    
   

    

     

    
    

     
    // if(root == NULL){
     
    
   

    

     

    
    

     
    // return NULL;
     
    
   

    

     

    
    

     
    // }
     
    
   

    

     

    
    

     
    // //交换左右节点
     
    
   

    

     

    
    

     
    // struct TreeNode* temp;
     
    
   

    

     

    
    

     
    // temp = root->left;
     
    
   

    

     

    
    

     
    // root->left = root->right;
     
    
   

    

     

    
    

     
    // root->right = temp;
     
    
   

    

     

    
    

     
    // //交换左子树
     
    
   

    

     

    
    

     
    // invertTree(root->left);
     
    
   

    

     

    
    

     
    // //交换右子树
     
    
   

    

     

    
    

     
    // invertTree(root->right);
     
    
   

    

     

    
    

     
    // //函数返回时就表示当前这个节点，以及它的左右子树都已经交换完了
     
    
   

    

     

    
    

     
    // return root;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    //方法二
     
    
   

    

     

    
    

     
    if(root == NULL){
     
    
   

    

     

    
    

     
        return NULL;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    //交换左子树节点
     
    
   

    

     

    
    

     
    struct TreeNode* left = invertTree(root->left);
     
    
   

    

     

    
    

     
    //交换右子树节点
     
    
   

    

     

    
    

     
    struct TreeNode* right = invertTree(root->right);
     
    
   

    

     

    
    

     
    //此时左右子树的节点都已经完成交换了，现在需要交换左右子树
     
    
   

    

     

    
    

     

          root->left = right;
     
    
   

    

     

    
    

     

          root->right = left;
     
    
   

    

     

    
    

     
    return root;
     
    
   

    

     

    
    

     

      }
     
    
  
 

结语

今天是力扣打卡第17天！

加油哦

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121324915