[leetcode二叉树系列]5 二叉树翻转

本文涉及知识点　

• 二叉树的遍历
• 栈的运用

二叉树的遍历和栈的相关概念前面已经介绍，忘记了的小伙伴复习后再看效果一定翻倍哟！

二叉树知识复习：[今天给二叉树加个BGM，二叉树唱歌了！]

队列知识复习：[leetcode栈队列]1 栈实现队列

1

Leetcode226 翻转二叉树

翻转一棵二叉树。。

示例1：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

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

小蓝希望大家在此思考1分钟，

效果更好哈！

01

题目解析

• 思路

思路阐述

首先我们的目标是将节点的左右值进行交换，说到这里小伙伴可以自行想想可以使用几种方法进行交换，其效率如何，为什么？ok,回到正题，这道题同样是交换，我们交换两个节点的值需要通过根节点的指针拿到左右节点的地址，交换完了以后我们还需要继续按照同样的方式进行交换，那么怎么保存这些节点，小伙伴们可以使用栈也可以使用队列，只不过顺序不同而已，这里咋们使用栈。

• 先看看示例中二叉树

• 从根节点访问，先将根节点4放入栈中。

• 从栈中取出4(注意是指针哟)，引入临时变量temp实现指针之间交换。与此同时记录两节点，分别入栈。

• 重复上面步骤直到栈空

02

代码实现

1

c++版本

2

python版本

3

java版本