【手把手带你刷LeetCode】——17.翻转二叉树(DFS)

wuchangjian2021-11-16 07:48:02编程学习

【前言】

今天是力扣打卡第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天!

加油哦

相关文章

react 项目打包优化 ===

目录 项目打包 项目本地预览 打包体积分析 生产环境优化 路由...

2021-2027全球与中国镀锡钢板市场现状及未来发展趋势

本报告研究全球与中国市场镀锡钢板的产能、产量、销量、销售额、价格及未来趋势。重点分析全...

Java基础---字符串(String)操作类

1.String类如何创建对象 String类---不可变的字符串操作类 S...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。