LeetCode刷题（121）～翻转二叉树【从上到下从下到上 递归 ｜ 迭代】

题目描述

翻转一棵二叉树。

示例：

输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1

解答

Demo（从上到下 依次交换左右节点）

TreeNode* invertTree(TreeNode* root) { if(root==NULL) return NULL; // 交换左右节点 TreeNode* temp=root->left; root->left=root->right; root->right=temp; // 递归 invertTree(root->left); invertTree(root->right); return root; }

运行结果 Demo（从下到上 依次递归）

TreeNode* invertTree(TreeNode* root) { if(root==NULL) return NULL; //递归 TreeNode* left=invertTree(root->left); TreeNode* right=invertTree(root->right); //左右交换 root->right=left; root->left=right; return root; }

运行结果 Demo（迭代）

TreeNode* invertTree(TreeNode* root) { if(root==NULL) return NULL; queue<TreeNode*> q; q.push(root); while(!q.empty()) { TreeNode* current=q.front(); q.pop(); // 交换左右节点 TreeNode* temp=current->right; current->right=current->left; current->left=temp; // 将左右节点再入队列 if(current->right) q.push(current->right); if(current->left) q.push(current->left); } return root; }

运行结果

题目来源

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/invert-binary-tree

海轰Pro 认证博客专家 C/C++ 微信小程序 微信小程序：「海轰Pro」微信公众号：「海轰Pro」知乎：「海轰Pro」微博：「海轰Pro」