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

题目描述

翻转一棵二叉树。

示例：

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

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

解答

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; }

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

运行结果

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; }

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

运行结果

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; }

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

运行结果

题目来源

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

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108378278