【数据结构与算法经典例题】翻转二叉树

用户11396077

发布于 2024-12-06 19:28:08

1010

文章被收录于专栏：C/C++指南

一、问题描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 原题出自 226. 翻转二叉树 - 力扣（LeetCode）

二、解题思路

解题思路: 翻转二叉树（也称为二叉树的镜像）是指对二叉树进行遍历，并交换每个节点的左右子树。通过递归调用可以快速简单的完成任务

首先对接收的二叉树根结点进行判断，如果该节点为空，直接返回NULL；如果该节点左右孩子为空，无需翻转，直接返回该结点地址
否则，交换左右指针——左指针指向右孩子，右指针指向左孩子
然后对左子树和右子树递归调用，对每一棵子树进行相同的判断和翻转，最后返回根结点

三、C语言实现代码

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    
};
typedef struct TreeNode TNode;
struct TreeNode* invertTree(struct TreeNode* root)
{
    if (root == NULL)//空树的情况
        return NULL;
    if (root->left == NULL && root->right == NULL)//没有子节点的情况
        return root;

    TNode* tmp = root->left;//左右指针交换
    root->left = root->right;
    root->right = tmp;

    invertTree(root->left);//对子树递归调用
    invertTree(root->right);
    return root;
}