offer 27 二叉树的镜像
文章目录
二叉树的镜像

定义
对于二叉树中任意节点 root ,设其左 / 右子节点分别为 left, right ;则在二叉树的镜像中的对应 root 节点,其左 / 右子节点分别为 right, left 。
方法一:递归法
- 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个节点的左 / 右子节点,即可生成二叉树的镜像。
- 当节点为空的时候,就说明已经交换完毕
- 需要先定义一个辅助节点,用来暂存交换的节点



方法二:辅助栈(或队列)
利用栈(或队列)遍历树的所有节点 nodenode ,并交换每个 nodenode 的左 / 右子节点。
- 先把根节点入栈,然后出战,然后左右节点入栈,再出栈,先进后出

- 这个栈看起来更直观

还是用linkedlist更好,stack都快被放弃了
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论