【手把手带你刷LeetCode】——17.翻转二叉树(DFS)
【前言】
今天是力扣打卡第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天!
加油哦